<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width,initial-scale=1" />
    <title>封装自己的专属集合Set | aiyoudiao</title>
    <meta name="generator" content="VuePress 1.9.10" />
    <link rel="icon" href="/img/blog.ico">
    <script src="https://cdn.jsdelivr.net/npm/live2d-widget@3.1.4/lib/L2Dwidget.min.js"></script> <meta name="description" content="码二~">
    <meta name="keywords" content="前端博客,个人技术博客,前端,前端开发,前端框架,web前端,前端面试题,技术文档,学习,面试,JavaScript,js,ES6,TypeScript,vue,python,css3,html5,Node,git,github,gitee,markdown">
    <meta name="theme-color" content="#11a8cd">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, minimum-scale=1.0, maximum-scale=1.0, user-scalable=no"> <link rel="preload" href="/assets/css/0.styles.146197cf.css" as="style"><link rel="preload" href="/assets/js/app.bd2fbc77.js" as="script"><link rel="preload" href="/assets/js/3.72c9c947.js" as="script"><link rel="preload" href="/assets/js/141.1f70e1c7.js" as="script"><link rel="preload" href="/assets/js/42.4251ca36.js" as="script"><link rel="prefetch" href="/assets/js/1.4ed4671d.js"><link rel="prefetch" href="/assets/js/10.bd6ddb58.js"><link rel="prefetch" href="/assets/js/100.20d2348f.js"><link rel="prefetch" href="/assets/js/101.ba7b784c.js"><link rel="prefetch" href="/assets/js/102.c3e2dcae.js"><link rel="prefetch" href="/assets/js/103.0f4c50f3.js"><link rel="prefetch" href="/assets/js/104.ef47a111.js"><link rel="prefetch" href="/assets/js/105.2e00f516.js"><link rel="prefetch" href="/assets/js/106.b50e19b9.js"><link rel="prefetch" href="/assets/js/107.e125a8f6.js"><link rel="prefetch" href="/assets/js/108.770493ab.js"><link rel="prefetch" href="/assets/js/109.74766d7b.js"><link rel="prefetch" href="/assets/js/11.f786a5ee.js"><link rel="prefetch" href="/assets/js/110.0b0ee5b4.js"><link rel="prefetch" href="/assets/js/111.835b0e44.js"><link rel="prefetch" href="/assets/js/112.352fa217.js"><link rel="prefetch" href="/assets/js/113.4e908557.js"><link rel="prefetch" href="/assets/js/114.7b77996d.js"><link rel="prefetch" href="/assets/js/115.bdc61268.js"><link rel="prefetch" href="/assets/js/116.d5da9b8b.js"><link rel="prefetch" href="/assets/js/117.35ab1f9f.js"><link rel="prefetch" href="/assets/js/118.517c151d.js"><link rel="prefetch" href="/assets/js/119.f7f49ba8.js"><link rel="prefetch" href="/assets/js/12.3c729a65.js"><link rel="prefetch" href="/assets/js/120.b559598b.js"><link rel="prefetch" href="/assets/js/121.bf8a2f43.js"><link rel="prefetch" href="/assets/js/122.11a0bc97.js"><link rel="prefetch" href="/assets/js/123.2bafdde7.js"><link rel="prefetch" href="/assets/js/124.dc393688.js"><link rel="prefetch" href="/assets/js/125.ed3f389a.js"><link rel="prefetch" href="/assets/js/126.8fd9a57d.js"><link rel="prefetch" href="/assets/js/127.3bf2a1f2.js"><link rel="prefetch" href="/assets/js/128.b9c671d3.js"><link rel="prefetch" href="/assets/js/129.5d331f0d.js"><link rel="prefetch" href="/assets/js/13.7b1a1fe5.js"><link rel="prefetch" href="/assets/js/130.53e4f9c6.js"><link rel="prefetch" href="/assets/js/131.dcc47e1d.js"><link rel="prefetch" href="/assets/js/132.692dcdcd.js"><link rel="prefetch" href="/assets/js/133.e293202c.js"><link rel="prefetch" href="/assets/js/134.593dccf2.js"><link rel="prefetch" href="/assets/js/135.d76d384b.js"><link rel="prefetch" href="/assets/js/136.a519c23c.js"><link rel="prefetch" href="/assets/js/137.b1821288.js"><link rel="prefetch" href="/assets/js/138.5bcea4ef.js"><link rel="prefetch" href="/assets/js/139.076664b0.js"><link rel="prefetch" href="/assets/js/14.35f257b2.js"><link rel="prefetch" href="/assets/js/140.a019e655.js"><link rel="prefetch" href="/assets/js/142.5ed728fd.js"><link rel="prefetch" href="/assets/js/143.1c8cdc78.js"><link rel="prefetch" href="/assets/js/144.b0cb125b.js"><link rel="prefetch" href="/assets/js/145.c0209a76.js"><link rel="prefetch" href="/assets/js/146.551469f4.js"><link rel="prefetch" href="/assets/js/147.1dfd721d.js"><link rel="prefetch" href="/assets/js/148.91d07ef5.js"><link rel="prefetch" href="/assets/js/149.5b88b710.js"><link rel="prefetch" href="/assets/js/15.23bbc29a.js"><link rel="prefetch" href="/assets/js/150.8301107f.js"><link rel="prefetch" href="/assets/js/151.867da089.js"><link rel="prefetch" href="/assets/js/152.935d5046.js"><link rel="prefetch" href="/assets/js/153.f39d8435.js"><link rel="prefetch" href="/assets/js/154.6b9eb2c3.js"><link rel="prefetch" href="/assets/js/155.14283ad4.js"><link rel="prefetch" href="/assets/js/156.2d7c1a2a.js"><link rel="prefetch" href="/assets/js/157.2f28d02f.js"><link rel="prefetch" href="/assets/js/158.151221ae.js"><link rel="prefetch" href="/assets/js/159.ef6d7ffe.js"><link rel="prefetch" href="/assets/js/16.1793aef7.js"><link rel="prefetch" href="/assets/js/160.de54c4ea.js"><link rel="prefetch" href="/assets/js/161.24d4e57c.js"><link rel="prefetch" href="/assets/js/162.632032fe.js"><link rel="prefetch" href="/assets/js/163.fd01cd99.js"><link rel="prefetch" href="/assets/js/164.45f203f5.js"><link rel="prefetch" href="/assets/js/165.aafe4fe1.js"><link rel="prefetch" href="/assets/js/166.1dd1d21c.js"><link rel="prefetch" href="/assets/js/167.5501b3a1.js"><link rel="prefetch" href="/assets/js/168.fbe58b1f.js"><link rel="prefetch" href="/assets/js/169.2cae7f5e.js"><link rel="prefetch" href="/assets/js/17.bbfe63f2.js"><link rel="prefetch" href="/assets/js/170.265f7c9e.js"><link rel="prefetch" href="/assets/js/171.b61f327d.js"><link rel="prefetch" href="/assets/js/172.5d0043fd.js"><link rel="prefetch" href="/assets/js/173.45284bb6.js"><link rel="prefetch" href="/assets/js/174.9130e0c4.js"><link rel="prefetch" href="/assets/js/175.2b38bddd.js"><link rel="prefetch" href="/assets/js/176.9772cf09.js"><link rel="prefetch" href="/assets/js/177.69048ebc.js"><link rel="prefetch" href="/assets/js/178.e10d7ce5.js"><link rel="prefetch" href="/assets/js/179.3789edc0.js"><link rel="prefetch" href="/assets/js/18.0807ded0.js"><link rel="prefetch" href="/assets/js/180.ab675e47.js"><link rel="prefetch" href="/assets/js/181.2e39eff0.js"><link rel="prefetch" href="/assets/js/19.becf5a76.js"><link rel="prefetch" href="/assets/js/2.eb089a4f.js"><link rel="prefetch" href="/assets/js/20.cea59652.js"><link rel="prefetch" href="/assets/js/21.58c43ff1.js"><link rel="prefetch" href="/assets/js/22.f73b825d.js"><link rel="prefetch" href="/assets/js/23.43b13730.js"><link rel="prefetch" href="/assets/js/24.f77f93ca.js"><link rel="prefetch" href="/assets/js/25.7dfaf3fb.js"><link rel="prefetch" href="/assets/js/26.629d28e5.js"><link rel="prefetch" href="/assets/js/27.4fff23ea.js"><link rel="prefetch" href="/assets/js/28.1b8ae389.js"><link rel="prefetch" href="/assets/js/29.d5cce9a0.js"><link rel="prefetch" href="/assets/js/30.961d5519.js"><link rel="prefetch" href="/assets/js/31.121dd1af.js"><link rel="prefetch" href="/assets/js/32.4a3c5df7.js"><link rel="prefetch" href="/assets/js/33.5537f44b.js"><link rel="prefetch" href="/assets/js/34.1d4d4653.js"><link rel="prefetch" href="/assets/js/35.d094209b.js"><link rel="prefetch" href="/assets/js/36.832660c5.js"><link rel="prefetch" href="/assets/js/37.145c3665.js"><link rel="prefetch" href="/assets/js/38.4f369bfe.js"><link rel="prefetch" href="/assets/js/39.ba060044.js"><link rel="prefetch" href="/assets/js/4.66d742f6.js"><link rel="prefetch" href="/assets/js/40.e50e0379.js"><link rel="prefetch" href="/assets/js/41.4ed7617c.js"><link rel="prefetch" href="/assets/js/43.d22b74c4.js"><link rel="prefetch" href="/assets/js/44.59439f9d.js"><link rel="prefetch" href="/assets/js/45.da28bc46.js"><link rel="prefetch" href="/assets/js/46.b8db1176.js"><link rel="prefetch" href="/assets/js/47.7ed16fc7.js"><link rel="prefetch" href="/assets/js/48.c982d5ed.js"><link rel="prefetch" href="/assets/js/49.a7579f55.js"><link rel="prefetch" href="/assets/js/5.08802d7d.js"><link rel="prefetch" href="/assets/js/50.103b5bf6.js"><link rel="prefetch" href="/assets/js/51.0fe9d79a.js"><link rel="prefetch" href="/assets/js/52.9ba31e26.js"><link rel="prefetch" href="/assets/js/53.0e8bc1f0.js"><link rel="prefetch" href="/assets/js/54.9566e517.js"><link rel="prefetch" href="/assets/js/55.a124abae.js"><link rel="prefetch" href="/assets/js/56.d9cf0800.js"><link rel="prefetch" href="/assets/js/57.93599da0.js"><link rel="prefetch" href="/assets/js/58.d943f85b.js"><link rel="prefetch" href="/assets/js/59.50a66488.js"><link rel="prefetch" href="/assets/js/6.a3ea60eb.js"><link rel="prefetch" href="/assets/js/60.21aa3aa3.js"><link rel="prefetch" href="/assets/js/61.6712c00f.js"><link rel="prefetch" href="/assets/js/62.eff3e4b1.js"><link rel="prefetch" href="/assets/js/63.09701d5a.js"><link rel="prefetch" href="/assets/js/64.eb440dec.js"><link rel="prefetch" href="/assets/js/65.aeed0579.js"><link rel="prefetch" href="/assets/js/66.97244c64.js"><link rel="prefetch" href="/assets/js/67.e01c5c24.js"><link rel="prefetch" href="/assets/js/68.21be91ba.js"><link rel="prefetch" href="/assets/js/69.c0849905.js"><link rel="prefetch" href="/assets/js/7.7fd40e91.js"><link rel="prefetch" href="/assets/js/70.b32bbe5d.js"><link rel="prefetch" href="/assets/js/71.0efbc0c7.js"><link rel="prefetch" href="/assets/js/72.ef963181.js"><link rel="prefetch" href="/assets/js/73.ca7dd5db.js"><link rel="prefetch" href="/assets/js/74.4483ede8.js"><link rel="prefetch" href="/assets/js/75.374ab483.js"><link rel="prefetch" href="/assets/js/76.b4a39f08.js"><link rel="prefetch" href="/assets/js/77.6b30c3cd.js"><link rel="prefetch" href="/assets/js/78.15376c33.js"><link rel="prefetch" href="/assets/js/79.3153fcec.js"><link rel="prefetch" href="/assets/js/80.9a88c684.js"><link rel="prefetch" href="/assets/js/81.1e3f842c.js"><link rel="prefetch" href="/assets/js/82.996dbd3d.js"><link rel="prefetch" href="/assets/js/83.955158bf.js"><link rel="prefetch" href="/assets/js/84.71bdc76d.js"><link rel="prefetch" href="/assets/js/85.774e49f2.js"><link rel="prefetch" href="/assets/js/86.bebf32e5.js"><link rel="prefetch" href="/assets/js/87.becdbde1.js"><link rel="prefetch" href="/assets/js/88.49e933f4.js"><link rel="prefetch" href="/assets/js/89.eeceedfd.js"><link rel="prefetch" href="/assets/js/90.3ea6dd12.js"><link rel="prefetch" href="/assets/js/91.62a6a556.js"><link rel="prefetch" href="/assets/js/92.e2ebb8f5.js"><link rel="prefetch" href="/assets/js/93.dcdefe7a.js"><link rel="prefetch" href="/assets/js/94.bf412146.js"><link rel="prefetch" href="/assets/js/95.8deadcdc.js"><link rel="prefetch" href="/assets/js/96.9977087a.js"><link rel="prefetch" href="/assets/js/97.6591f9da.js"><link rel="prefetch" href="/assets/js/98.4db7f75e.js"><link rel="prefetch" href="/assets/js/99.a61462e9.js"><link rel="prefetch" href="/assets/js/vendors~docsearch.2852b102.js"> <link rel="stylesheet" href="/assets/css/0.styles.146197cf.css">
  </head>
  <body class="theme-mode-light">
    <div id="app" data-server-rendered="true"><div class="theme-container sidebar-open have-rightmenu"><header class="navbar blur"><div title="目录" class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" width="50" height="50" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><img src="https://p3-passport.byteacctimg.com/img/user-avatar/794fdae4ff249d532da19a3c26d420ed~300x300.image" alt="aiyoudiao" class="logo"> <span class="site-name can-hide">
      aiyoudiao
    </span></a> <div class="links"><div class="sky-switch" data-v-3a03d589><label for="toggle" data-v-3a03d589><input id="toggle" type="checkbox" data-v-3a03d589><div data-v-3a03d589></div></label></div> <div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="笔记" class="dropdown-title"><!----> <span class="title" style="display:;">笔记</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/84633490449/" class="nav-link">
  JavaScript
</a></li><li class="dropdown-item"><!----> <a href="/pages/2331001041/" class="nav-link">
  Vue
</a></li><li class="dropdown-item"><!----> <a href="/pages/18114480448/" class="nav-link">
  React
</a></li><li class="dropdown-item"><!----> <a href="/pages/25236260426/" class="nav-link">
  低代码
</a></li><li class="dropdown-item"><!----> <a href="/pages/35345230523/" class="nav-link">
  线性系统
</a></li><li class="dropdown-item"><!----> <a href="/pages/08313561056/" class="nav-link">
  暂未分类
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="算法与设计" class="dropdown-title"><!----> <span class="title" style="display:;">算法与设计</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/70741550255/" class="nav-link">
  LeetCode
</a></li><li class="dropdown-item"><!----> <a href="/pages/17845450445/" class="nav-link">
  算法
</a></li><li class="dropdown-item"><!----> <a href="/pages/90132170217/" class="nav-link">
  数据结构
</a></li><li class="dropdown-item"><!----> <a href="/pages/50546120212/" class="nav-link">
  设计模式
</a></li><li class="dropdown-item"><!----> <a href="/pages/02344550255/" class="nav-link">
  Other
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="技能" class="dropdown-title"><!----> <span class="title" style="display:;">技能</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/82158160216/" class="nav-link">
  PMP
</a></li><li class="dropdown-item"><!----> <a href="/pages/41858590259/" class="nav-link">
  Office
</a></li><li class="dropdown-item"><!----> <a href="/pages/02359360236/" class="nav-link">
  面试
</a></li><li class="dropdown-item"><!----> <a href="/pages/73600130213/" class="nav-link">
  Bash
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="历程" class="dropdown-title"><!----> <span class="title" style="display:;">历程</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/83857320232/" class="nav-link">
  流年往事
</a></li><li class="dropdown-item"><!----> <a href="/pages/93419130213/" class="nav-link">
  经验片段
</a></li><li class="dropdown-item"><!----> <a href="/pages/99744220322/" class="nav-link">
  读书杂感
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="首页" class="dropdown-title"><!----> <span class="title" style="display:;">首页</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/archives/" class="nav-link">
  归档
</a></li><li class="dropdown-item"><!----> <a href="/categories/" class="nav-link">
  分类
</a></li><li class="dropdown-item"><!----> <a href="/tags/" class="nav-link">
  标签
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="其它" class="dropdown-title"><!----> <span class="title" style="display:;">其它</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/02657130213/" class="nav-link">
  简介
</a></li><li class="dropdown-item"><!----> <a href="/pages/5390102042/" class="nav-link">
  收藏
</a></li><li class="dropdown-item"><!----> <a href="/pages/32309510451/" class="nav-link">
  有趣
</a></li><li class="dropdown-item"><!----> <a href="/pages/23313210521/" class="nav-link">
  文档
</a></li></ul></div></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <div class="sidebar-hover-trigger"></div> <aside class="sidebar" style="display:none;"><div class="blogger"><img src="/img/mar.jpg"> <div class="blogger-info"><h3>码二</h3> <span>扫微信二维码，认识一下码二吧😉。</span></div></div> <nav class="nav-links"><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="笔记" class="dropdown-title"><!----> <span class="title" style="display:;">笔记</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/84633490449/" class="nav-link">
  JavaScript
</a></li><li class="dropdown-item"><!----> <a href="/pages/2331001041/" class="nav-link">
  Vue
</a></li><li class="dropdown-item"><!----> <a href="/pages/18114480448/" class="nav-link">
  React
</a></li><li class="dropdown-item"><!----> <a href="/pages/25236260426/" class="nav-link">
  低代码
</a></li><li class="dropdown-item"><!----> <a href="/pages/35345230523/" class="nav-link">
  线性系统
</a></li><li class="dropdown-item"><!----> <a href="/pages/08313561056/" class="nav-link">
  暂未分类
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="算法与设计" class="dropdown-title"><!----> <span class="title" style="display:;">算法与设计</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/70741550255/" class="nav-link">
  LeetCode
</a></li><li class="dropdown-item"><!----> <a href="/pages/17845450445/" class="nav-link">
  算法
</a></li><li class="dropdown-item"><!----> <a href="/pages/90132170217/" class="nav-link">
  数据结构
</a></li><li class="dropdown-item"><!----> <a href="/pages/50546120212/" class="nav-link">
  设计模式
</a></li><li class="dropdown-item"><!----> <a href="/pages/02344550255/" class="nav-link">
  Other
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="技能" class="dropdown-title"><!----> <span class="title" style="display:;">技能</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/82158160216/" class="nav-link">
  PMP
</a></li><li class="dropdown-item"><!----> <a href="/pages/41858590259/" class="nav-link">
  Office
</a></li><li class="dropdown-item"><!----> <a href="/pages/02359360236/" class="nav-link">
  面试
</a></li><li class="dropdown-item"><!----> <a href="/pages/73600130213/" class="nav-link">
  Bash
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="历程" class="dropdown-title"><!----> <span class="title" style="display:;">历程</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/83857320232/" class="nav-link">
  流年往事
</a></li><li class="dropdown-item"><!----> <a href="/pages/93419130213/" class="nav-link">
  经验片段
</a></li><li class="dropdown-item"><!----> <a href="/pages/99744220322/" class="nav-link">
  读书杂感
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="首页" class="dropdown-title"><!----> <span class="title" style="display:;">首页</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/archives/" class="nav-link">
  归档
</a></li><li class="dropdown-item"><!----> <a href="/categories/" class="nav-link">
  分类
</a></li><li class="dropdown-item"><!----> <a href="/tags/" class="nav-link">
  标签
</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="其它" class="dropdown-title"><!----> <span class="title" style="display:;">其它</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/pages/02657130213/" class="nav-link">
  简介
</a></li><li class="dropdown-item"><!----> <a href="/pages/5390102042/" class="nav-link">
  收藏
</a></li><li class="dropdown-item"><!----> <a href="/pages/32309510451/" class="nav-link">
  有趣
</a></li><li class="dropdown-item"><!----> <a href="/pages/23313210521/" class="nav-link">
  文档
</a></li></ul></div></div> <!----></nav>  <ul class="sidebar-links"><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>LeetCode</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>算法</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading open"><span>数据结构</span> <span class="arrow down"></span></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/pages/90132170217/" class="sidebar-link">浅聊数据结构(和算法)</a></li><li><a href="/pages/9384806026/" class="sidebar-link">封装自己的专属数组</a></li><li><a href="/pages/35925130313/" class="sidebar-link">通过封装来学习栈</a></li><li><a href="/pages/45502270327/" class="sidebar-link">通过封装来学习队列</a></li><li><a href="/pages/24249530353/" class="sidebar-link">封装自己的专属链表</a></li><li><a href="/pages/72920260326/" class="sidebar-link">通过链表来思考递归</a></li><li><a href="/pages/7445103033/" class="sidebar-link">封装自己的专属二分搜索树篇上</a></li><li><a href="/pages/67506300330/" class="sidebar-link">封装自己的专属二分搜索树篇下</a></li><li><a href="/pages/64940340334/" aria-current="page" class="active sidebar-link">封装自己的专属集合Set</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/pages/64940340334/#前言" class="sidebar-link">前言</a></li><li class="sidebar-sub-header"><a href="/pages/64940340334/#集合的应用" class="sidebar-link">集合的应用</a></li><li class="sidebar-sub-header"><a href="/pages/64940340334/#基于二分搜索树的实现集合" class="sidebar-link">基于二分搜索树的实现集合</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/pages/64940340334/#集合接口" class="sidebar-link">集合接口</a></li><li class="sidebar-sub-header"><a href="/pages/64940340334/#代码示例" class="sidebar-link">代码示例</a></li></ul></li><li class="sidebar-sub-header"><a href="/pages/64940340334/#集合-基于链表的实现" class="sidebar-link">集合-基于链表的实现</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/pages/64940340334/#集合接口-2" class="sidebar-link">集合接口</a></li><li class="sidebar-sub-header"><a href="/pages/64940340334/#代码示例-2" class="sidebar-link">代码示例</a></li></ul></li><li class="sidebar-sub-header"><a href="/pages/64940340334/#集合类的复杂度分析" class="sidebar-link">集合类的复杂度分析</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/pages/64940340334/#mylinkedlistset-与-mybstset-时间复杂度对比" class="sidebar-link">MyLinkedListSet 与 MyBSTSet 时间复杂度对比</a></li><li class="sidebar-sub-header"><a href="/pages/64940340334/#二分搜索树的局限性" class="sidebar-link">二分搜索树的局限性</a></li><li class="sidebar-sub-header"><a href="/pages/64940340334/#log-n-和-n-的差距" class="sidebar-link">log n 和 n 的差距</a></li><li class="sidebar-sub-header"><a href="/pages/64940340334/#mylinkedlistset" class="sidebar-link">MyLinkedListSet</a></li><li class="sidebar-sub-header"><a href="/pages/64940340334/#mybstset" class="sidebar-link">MyBSTSet</a></li><li class="sidebar-sub-header"><a href="/pages/64940340334/#二分搜索树" class="sidebar-link">二分搜索树</a></li><li class="sidebar-sub-header"><a href="/pages/64940340334/#代码示例-3" class="sidebar-link">代码示例</a></li></ul></li><li class="sidebar-sub-header"><a href="/pages/64940340334/#总结" class="sidebar-link">总结</a></li><li class="sidebar-sub-header"><a href="/pages/64940340334/#拓展" class="sidebar-link">拓展</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/pages/64940340334/#leetcode-804-唯一摩尔斯密码词" class="sidebar-link">leetcode 804.唯一摩尔斯密码词</a></li><li class="sidebar-sub-header"><a href="/pages/64940340334/#有序集合和无序集合" class="sidebar-link">有序集合和无序集合</a></li><li class="sidebar-sub-header"><a href="/pages/64940340334/#多重集合" class="sidebar-link">多重集合</a></li></ul></li></ul></li><li><a href="/pages/3284303033/" class="sidebar-link">封装自己的专属映射Map</a></li><li><a href="/pages/06634350335/" class="sidebar-link">封装自己的专属堆Heap</a></li><li><a href="/pages/23101220422/" class="sidebar-link">封装自己的优先队列PriorityQueue</a></li><li><a href="/pages/0300408048/" class="sidebar-link">封装自己的专属线段树SegmentTree</a></li></ul></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>设计模式</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>Other</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>vue3设计与实现</span> <span class="arrow right"></span></p> <!----></section></li></ul> </aside> <div><main class="page"> <div class="theme-vdoing-wrapper bg-style-1"><div class="articleInfo-wrap" data-v-18fb2c02><div class="articleInfo" data-v-18fb2c02><ul class="breadcrumbs" data-v-18fb2c02><li data-v-18fb2c02><a href="/" title="首页" class="iconfont icon-home router-link-active" data-v-18fb2c02></a></li> <li data-v-18fb2c02><a href="/categories/?category=%E7%AE%97%E6%B3%95%E4%B8%8E%E8%AE%BE%E8%AE%A1" title="分类" data-v-18fb2c02>
          算法与设计
        </a></li> <li data-v-18fb2c02><a href="/categories/?category=%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84" title="分类" data-v-18fb2c02>
          数据结构
        </a></li> <!----></ul> <div class="info" data-v-18fb2c02><div title="作者" class="author iconfont icon-touxiang" data-v-18fb2c02><a href="javascript:;" data-v-18fb2c02>aiyoudiao</a></div> <div title="创建时间" class="date iconfont icon-riqi" data-v-18fb2c02><a href="javascript:;" data-v-18fb2c02>2022-03-27</a></div> <!----></div></div></div> <!----> <div class="content-wrapper"><div class="right-menu-wrapper"><div class="right-menu-margin"><div class="right-menu-content"></div></div></div> <h1><!----> <span>
            封装自己的专属集合Set
          </span></h1> <div class="theme-vdoing-content content__default"><h2 id="前言"><a href="#前言" class="header-anchor">#</a> 前言</h2> <p>集合是高层的数据结构，高层的数据结构还有栈和队列，这种数据结构更像是定义好了这种数据结构的相应的使用接口。<br>
有了这些使用的接口包括这些数据结构本身所维持的一些性质，就可以非常容易的把它们放入一些具体的应用中，但是底层实现可以是多种多样的。<br>
比如栈和队列的底层实现即可以是动态数组也可以是链表，集合 Set 也是类似这样的数据结构。</p> <p>还是那句老话：光看文章能够掌握两成，动手敲代码、动脑思考、画图才可以掌握八成。<a href="https://link.juejin.cn/?target=https%3A%2F%2Fgithub.com%2Faiyoudiao%2FMaoDataStructures" target="_blank" rel="noopener noreferrer">源码仓库<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p><strong>不要完美主义。掌握好“度”。</strong></p> <p>太过于追求完美会把自己逼的太紧，会产生各种焦虑的心态，最后甚至会怀疑自己，温故而知新，不要停止不前，掌握好这个度，不存在你把那些你认为完全掌握了，然后就成了某一个领域的专家，相反一旦你产生很浓厚的厌恶感，那么就意味着你即将会放弃或者已经选择了放弃，虽然你之前想把它做到 100 分，但是由于你的放弃让它变为 0 分。</p> <p>学习本着自己的目标去。不要在学的过程中偏离了自己的目标。要分清主次。
难的东西，你可以慢慢的回头看一看。那样才会更加的柳暗花明，更能提升自己的收获。</p> <h2 id="集合的应用"><a href="#集合的应用" class="header-anchor">#</a> 集合的应用</h2> <p>典型的应用：用于客户的统计。<br>
如你做一个网站，对访问的 ip 进行一个统计，不仅要关注总访问量，还要关注有多少不同的 ip 访问，或者今天跟昨天相比又有多少个新的 ip 来访问，在这种时候就应该使用集合这种数据结构来做统计。</p> <p>典型的应用：词汇量的统计。<br>
在进行英文阅读的时候你会去参考，这本书的词汇量究竟有多少，对于一本书的词汇量来说，相同的单词是只记一次的，在这种时候就应该使用集合这种数据结构来做统计。</p> <p>接下来就基于之前实现的二分搜索树以及链表来进行集合的实现。</p> <h2 id="基于二分搜索树的实现集合"><a href="#基于二分搜索树的实现集合" class="header-anchor">#</a> 基于二分搜索树的实现集合</h2> <p>集合就是承载元素的一个容器，在集合中有一个非常重要的特点，也就是每个元素只能存在一次。在具体应用的时候需要这样的数据结构，它能够帮助你非常快速的进行去重这个工作，去重指的是去除所有重复的元素，让所有的元素只保留一份。例如你想统计一个饭馆有多少位会员，这时候你就需要进行一个去重的操作，会员不能够重复，无论是新客户还是老客户都只能手持一张会员卡。</p> <p>在二分搜索树的添加操作的时候，最开始实现的时候是不能盛放重复元素的，所以这个二分搜索树本身就是一个非常好的实现“集合”的底层数据结构。</p> <h3 id="集合接口"><a href="#集合接口" class="header-anchor">#</a> 集合接口</h3> <p><code>MySet</code></p> <p><code>void add (e)</code> : 不能添加重复元素<br> <code>void remove (e)</code><br> <code>boolean conatains (e)</code><br> <code>int getSize ()</code><br> <code>boolean isEmpty ()</code></p> <p>使用 MyBSTSet 来实现这个集合的接口</p> <h3 id="代码示例"><a href="#代码示例" class="header-anchor">#</a> 代码示例</h3> <p><code>(class: MyBinarySearchTree, class: MyBSTSet, class: Main)</code></p> <p><strong>MyBinarySearchTree</strong></p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token comment">// 自定义二分搜索树节点</span>
<span class="token keyword">class</span> <span class="token class-name">MyBinarySearchTreeNode</span> <span class="token punctuation">{</span>
    <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token parameter">element<span class="token punctuation">,</span> left <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">,</span> right <span class="token operator">=</span> <span class="token keyword">null</span></span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 实际存储的元素</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>element <span class="token operator">=</span> element<span class="token punctuation">;</span>
        <span class="token comment">// 当前节点的左子树</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>left <span class="token operator">=</span> left<span class="token punctuation">;</span>
        <span class="token comment">// 当前节点的右子树</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>right <span class="token operator">=</span> right<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

<span class="token comment">// 自定义二分搜索树</span>
<span class="token keyword">class</span> <span class="token class-name">MyBinarySearchTree</span> <span class="token punctuation">{</span>
    <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>root <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>size <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 添加元素到二分搜索树中 +</span>
    <span class="token function">add</span><span class="token punctuation">(</span><span class="token parameter">element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>element <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">Error</span><span class="token punctuation">(</span><span class="token string">&quot;element is null. can't store.&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">this</span><span class="token punctuation">.</span>root <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveAdd</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">,</span> element<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 添加元素到二分搜索树中  递归算法 -</span>
    <span class="token function">recursiveAdd</span><span class="token punctuation">(</span><span class="token parameter">node<span class="token punctuation">,</span> newElement</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 解决最基本的问题 也就是递归函数调用的终止条件</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token operator">++</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> <span class="token keyword">new</span> <span class="token class-name">MyBinarySearchTreeNode</span><span class="token punctuation">(</span>newElement<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 1. 当前节点的元素比新元素大</span>
        <span class="token comment">// 那么新元素就会被添加到当前节点的左子树去</span>
        <span class="token comment">// 2. 当前节点的元素比新元素小</span>
        <span class="token comment">// 那么新元素就会被添加到当前节点的右子树去</span>
        <span class="token comment">// 3. 当前节点的元素比新元素相等</span>
        <span class="token comment">// 什么都不做了，因为目前不添加重复的元素</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">compare</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">,</span> newElement<span class="token punctuation">)</span> <span class="token operator">&gt;</span> <span class="token number">0</span><span class="token punctuation">)</span>
        node<span class="token punctuation">.</span>left <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveAdd</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>left<span class="token punctuation">,</span> newElement<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">compare</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">,</span> newElement<span class="token punctuation">)</span> <span class="token operator">&lt;</span> <span class="token number">0</span><span class="token punctuation">)</span>
        node<span class="token punctuation">.</span>right <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveAdd</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">,</span> newElement<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">else</span> <span class="token punctuation">{</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 将复杂问题分解成多个性质相同的小问题，</span>
        <span class="token comment">// 然后求出小问题的答案，</span>
        <span class="token comment">// 最终构建出原问题的答案</span>
        <span class="token keyword">return</span> node<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 判断二分搜索树中是否包含某个元素 +</span>
    <span class="token function">contains</span><span class="token punctuation">(</span><span class="token parameter">element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">Error</span><span class="token punctuation">(</span><span class="token string">&quot;root is null. can't query.&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveContains</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">,</span> element<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 判断二分搜索树种是否包含某个元素 递归算法 -</span>
    <span class="token function">recursiveContains</span><span class="token punctuation">(</span><span class="token parameter">node<span class="token punctuation">,</span> element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span>

        <span class="token comment">// 当前节点元素比 要搜索的元素 大</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">compare</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">,</span> element<span class="token punctuation">)</span> <span class="token operator">&gt;</span> <span class="token number">0</span><span class="token punctuation">)</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveContains</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>left<span class="token punctuation">,</span> element<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">compare</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">,</span> element<span class="token punctuation">)</span> <span class="token operator">&lt;</span> <span class="token number">0</span><span class="token punctuation">)</span>
        <span class="token comment">// 当前元素比 要搜索的元素 小</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveContains</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">,</span> element<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment">// 两个元素相等</span>
        <span class="token keyword">else</span> <span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 找到二分搜索树中的最大值的元素 +</span>
    <span class="token function">maximum</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>size <span class="token operator">===</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">Error</span><span class="token punctuation">(</span><span class="token string">'binary search tree is empty.'</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveMaximum</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">)</span><span class="token punctuation">.</span>element<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 找到二分搜索树中的最大值的元素的节点 递归算法 -</span>
    <span class="token function">recursiveMaximum</span><span class="token punctuation">(</span><span class="token parameter">node</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 解决最基本的问题  向右走再也走不动了，说明当前节点就是最大值节点。</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>right <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span> node<span class="token punctuation">;</span>

        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveMaximum</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 删除二分搜索树中最大值的元素的节点，并返回这个节点的元素 +</span>
    <span class="token function">removeMax</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> maxElement <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">maximum</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>root <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveRemoveMax</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> maxElement<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 删除二分搜索树中最大值的元素的节点，并返回这个节点 递归算法 -</span>
    <span class="token function">recursiveRemoveMax</span><span class="token punctuation">(</span><span class="token parameter">node</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>right <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 先存 当前这个节点的左子树，</span>
        <span class="token comment">// 因为可能当前这个节点仅仅没有右子树，只有左子树，</span>
        <span class="token comment">// 那么左子树可以替代当前这个节点。</span>
        <span class="token keyword">let</span> leftNode <span class="token operator">=</span> node<span class="token punctuation">.</span>left<span class="token punctuation">;</span>
        node<span class="token punctuation">.</span>left <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token operator">--</span><span class="token punctuation">;</span>

        <span class="token keyword">return</span> leftNode<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        node<span class="token punctuation">.</span>right <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveRemoveMax</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> node<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 找到二分搜索树中的最小值 +</span>
    <span class="token function">minimum</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>size <span class="token operator">===</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">Error</span><span class="token punctuation">(</span><span class="token string">'binary search tree is empty.'</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveMinimum</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">)</span><span class="token punctuation">.</span>element<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 找到二分搜索树中的最小值的元素的节点 递归算法 -</span>
    <span class="token function">recursiveMinimum</span><span class="token punctuation">(</span><span class="token parameter">node</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>left <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span> node<span class="token punctuation">;</span>

        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveMinimum</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>left<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 删除二分搜索树中最小值的元素的节点，并返回这个节点的元素 +</span>
    <span class="token function">removeMin</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> leftNode <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">minimum</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>root <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveRemoveMin</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> leftNode<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 删除二分搜索树中最小值的元素的节点，并返回这个节点 递归算法 -</span>
    <span class="token function">recursiveRemoveMin</span><span class="token punctuation">(</span><span class="token parameter">node</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 解决最简单的问题</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>left <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> rightNode <span class="token operator">=</span> node<span class="token punctuation">.</span>right<span class="token punctuation">;</span>
        node<span class="token punctuation">.</span>right <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token operator">--</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> rightNode<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 将复杂的问题拆分为性质相同的小问题，</span>
        <span class="token comment">// 然后求出这些小问题的解后构建出原问题的答案</span>
        node<span class="token punctuation">.</span>left <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveRemoveMin</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>left<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> node<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 删除二分搜索树上的任意节点</span>
    <span class="token function">remove</span><span class="token punctuation">(</span><span class="token parameter">element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>root <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveRemove</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">,</span> element<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 删除二分搜索树上的任意节点 递归算法</span>
    <span class="token comment">// 返回删除对应元素节点后新的二分搜索树的根</span>
    <span class="token function">recursiveRemove</span><span class="token punctuation">(</span><span class="token parameter">node<span class="token punctuation">,</span> element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token keyword">null</span><span class="token punctuation">;</span>

        <span class="token comment">// 当前节点的元素值比待删除的元素小  那么就向当前节点的右子树中去找</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">compare</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">,</span> element<span class="token punctuation">)</span> <span class="token operator">&lt;</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        node<span class="token punctuation">.</span>right <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveRemove</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">,</span> element<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> node<span class="token punctuation">;</span>
        <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">compare</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">,</span> element<span class="token punctuation">)</span> <span class="token operator">&gt;</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 向当前节点的左子树中去找</span>
        node<span class="token punctuation">.</span>left <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveRemove</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>left<span class="token punctuation">,</span> element<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> node<span class="token punctuation">;</span>
        <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
        <span class="token comment">// 如果找到了相同值的节点了，开始进行相应的处理</span>

        <span class="token comment">// 如果这个节点左子树为空，那么就让这个节点的右子树覆盖当前节点</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>left <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">let</span> rightNode <span class="token operator">=</span> node<span class="token punctuation">.</span>right<span class="token punctuation">;</span>
            node<span class="token punctuation">.</span>right <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
            <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token operator">--</span><span class="token punctuation">;</span>
            <span class="token keyword">return</span> rightNode<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 如果当前节点的右子树为空，那么就让这个节点的左子树覆盖当前节点</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>right <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">let</span> leftNode <span class="token operator">=</span> node<span class="token punctuation">.</span>left<span class="token punctuation">;</span>
            node<span class="token punctuation">.</span>left <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
            <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token operator">--</span><span class="token punctuation">;</span>
            <span class="token keyword">return</span> leftNode<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 如果当前节点的左右子树都不为空，那么就开始特殊操作</span>
        <span class="token comment">// 1. 先找到当前节点右子树上最小的那个节点，保存起来</span>
        <span class="token comment">// 2. 然后删除掉当前节点右子树上最小的那个节点，</span>
        <span class="token comment">// 3. 让保存起来的那个节点覆盖掉当前节点</span>
        <span class="token comment">//    1. 也就是保存起来的那个节点的right = 删除掉当前节点右子树上最小的节点后返回的那个节点</span>
        <span class="token comment">//    2. 再让保存起来的那个节点的left = 当前节点的left</span>
        <span class="token comment">// 4. 解除当前节点及其left和right，全都赋值为null，这样就相当于把当前节点从二分搜索树中剔除了</span>
        <span class="token comment">// 5. 返回保存的这个节点</span>

        <span class="token keyword">let</span> successtor <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveMinimum</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">)</span><span class="token punctuation">;</span>
        successtor<span class="token punctuation">.</span>right <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveRemoveMin</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token comment">// 恢复removeMin 操作的this.size -- 带来的影响</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token operator">++</span><span class="token punctuation">;</span>

        successtor<span class="token punctuation">.</span>left <span class="token operator">=</span> node<span class="token punctuation">.</span>left<span class="token punctuation">;</span>

        <span class="token comment">// 开始正式的删除当前节点的操作</span>
        node <span class="token operator">=</span> node<span class="token punctuation">.</span>left <span class="token operator">=</span> node<span class="token punctuation">.</span>right <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token operator">--</span><span class="token punctuation">;</span>

        <span class="token comment">// 返回当前保存的节点</span>
        <span class="token keyword">return</span> successtor<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 前序遍历 +</span>
    <span class="token function">preOrder</span><span class="token punctuation">(</span><span class="token parameter">operator</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursivePreOrder</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">,</span> operator<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 前序遍历 递归算法 -</span>
    <span class="token function">recursivePreOrder</span><span class="token punctuation">(</span><span class="token parameter">node<span class="token punctuation">,</span> operator</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span><span class="token punctuation">;</span>

        <span class="token comment">// 调用一下操作方法</span>
        <span class="token function">operator</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>
        console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>node<span class="token punctuation">,</span> node<span class="token punctuation">.</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token comment">// 继续递归遍历左右子树</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursivePreOrder</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>left<span class="token punctuation">,</span> operator<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursivePreOrder</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">,</span> operator<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 前序遍历 非递归算法 +</span>
    <span class="token function">nonRecursivePreOrder</span><span class="token punctuation">(</span><span class="token parameter">operator</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> stack <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">MyLinkedListStack</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        stack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token operator">!</span>stack<span class="token punctuation">.</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 出栈操作</span>
        node <span class="token operator">=</span> stack<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token function">operator</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 访问当前的节点</span>
        console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token comment">// 栈是先入后出的，把需要后访问的节点 先放进去，先访问的节点后放进去</span>
        <span class="token comment">// 前序遍历是访问当前节点，然后再遍历左子树，最后遍历右子树</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>right <span class="token operator">!==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> stack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>left <span class="token operator">!==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> stack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>left<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 中序遍历 +</span>
    <span class="token function">inOrder</span><span class="token punctuation">(</span><span class="token parameter">operator</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveInOrder</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">,</span> operator<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 中序遍历 递归算法 -</span>
    <span class="token function">recursiveInOrder</span><span class="token punctuation">(</span><span class="token parameter">node<span class="token punctuation">,</span> operator</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span><span class="token punctuation">;</span>

        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveInOrder</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>left<span class="token punctuation">,</span> operator<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token function">operator</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>
        console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveInOrder</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">,</span> operator<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 后序遍历 +</span>
    <span class="token function">postOrder</span><span class="token punctuation">(</span><span class="token parameter">operator</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursivePostOrder</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">,</span> operator<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 后序遍历 递归算法 -</span>
    <span class="token function">recursivePostOrder</span><span class="token punctuation">(</span><span class="token parameter">node<span class="token punctuation">,</span> operator</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span><span class="token punctuation">;</span>

        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursivePostOrder</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>left<span class="token punctuation">,</span> operator<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursivePostOrder</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">,</span> operator<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token function">operator</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>
        console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 层序遍历</span>
    <span class="token function">levelOrder</span><span class="token punctuation">(</span><span class="token parameter">operator</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> queue <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">MyLinkedListQueue</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        queue<span class="token punctuation">.</span><span class="token function">enqueue</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token operator">!</span>queue<span class="token punctuation">.</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        node <span class="token operator">=</span> queue<span class="token punctuation">.</span><span class="token function">dequeue</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token function">operator</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>
        console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token comment">// 队列 是先进先出的，所以从左往右入队</span>
        <span class="token comment">// 栈  是后进先出的， 所以从右往左入栈</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>left <span class="token operator">!==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> queue<span class="token punctuation">.</span><span class="token function">enqueue</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>left<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>right <span class="token operator">!==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> queue<span class="token punctuation">.</span><span class="token function">enqueue</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 获取二分搜索树中节点个数 +</span>
    <span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 返回二分搜索树是否为空的bool值 +</span>
    <span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>size <span class="token operator">===</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 新增一个比较的方法，专门用来比较新增的元素大小 -</span>
    <span class="token comment">// 第一个元素比第二个元素大 就返回 1</span>
    <span class="token comment">// 第一个元素比第二个元素小 就返回 -1</span>
    <span class="token comment">// 第一个元素比第二个元素相等 就返回 0</span>
    <span class="token function">compare</span><span class="token punctuation">(</span><span class="token parameter">elementA<span class="token punctuation">,</span> elementB</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>elementA <span class="token operator">===</span> <span class="token keyword">null</span> <span class="token operator">||</span> elementB <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span>
        <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">Error</span><span class="token punctuation">(</span><span class="token string">&quot;element is null. can't compare.&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token comment">// 先直接写死</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>elementA <span class="token operator">&gt;</span> elementB<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>elementA <span class="token operator">&lt;</span> elementB<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token keyword">else</span> <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 输出二分搜索树中的信息</span>
    <span class="token comment">// @Override toString 2018-11-03-jwl</span>
    <span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> treeInfo <span class="token operator">=</span> <span class="token string">''</span><span class="token punctuation">;</span>
        treeInfo <span class="token operator">+=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">getBinarySearchTreeString</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> treeInfo<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> treeInfo<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 写一个辅助函数，用来生成二分搜索树信息的字符串</span>
    <span class="token function">getBinarySearchTreeString</span><span class="token punctuation">(</span>node<span class="token punctuation">,</span> depth<span class="token punctuation">,</span> treeInfo<span class="token punctuation">,</span> pageContent <span class="token operator">=</span> <span class="token string">''</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">//以前序遍历的方式</span>

        <span class="token keyword">if</span> <span class="token punctuation">(</span>node <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        treeInfo <span class="token operator">+=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">getDepthString</span><span class="token punctuation">(</span>depth<span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token string">'null \r\n'</span><span class="token punctuation">;</span>

        pageContent <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">getDepthString</span><span class="token punctuation">(</span>depth<span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token string">'null&lt;br /&gt;&lt;br /&gt;'</span><span class="token punctuation">;</span>
        document<span class="token punctuation">.</span>body<span class="token punctuation">.</span>innerHTML <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>pageContent<span class="token interpolation-punctuation punctuation">}</span></span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>

        <span class="token keyword">return</span> treeInfo<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        treeInfo <span class="token operator">+=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">getDepthString</span><span class="token punctuation">(</span>depth<span class="token punctuation">)</span> <span class="token operator">+</span> node<span class="token punctuation">.</span>element <span class="token operator">+</span> <span class="token string">'\r\n'</span><span class="token punctuation">;</span>

        pageContent <span class="token operator">=</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">getDepthString</span><span class="token punctuation">(</span>depth<span class="token punctuation">)</span> <span class="token operator">+</span> node<span class="token punctuation">.</span>element <span class="token operator">+</span> <span class="token string">'&lt;br /&gt;&lt;br /&gt;'</span><span class="token punctuation">;</span>
        document<span class="token punctuation">.</span>body<span class="token punctuation">.</span>innerHTML <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>pageContent<span class="token interpolation-punctuation punctuation">}</span></span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>

        treeInfo <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">getBinarySearchTreeString</span><span class="token punctuation">(</span>
        node<span class="token punctuation">.</span>left<span class="token punctuation">,</span>
        depth <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span>
        treeInfo
        <span class="token punctuation">)</span><span class="token punctuation">;</span>
        treeInfo <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">getBinarySearchTreeString</span><span class="token punctuation">(</span>
        node<span class="token punctuation">.</span>right<span class="token punctuation">,</span>
        depth <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span>
        treeInfo
        <span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">return</span> treeInfo<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 写一个辅助函数，用来生成递归深度字符串</span>
    <span class="token function">getDepthString</span><span class="token punctuation">(</span><span class="token parameter">depth</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> depthString <span class="token operator">=</span> <span class="token string">''</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> depth<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        depthString <span class="token operator">+=</span> <span class="token string">'-- '</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> depthString<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><p><strong>MyBSTSet</strong></p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token comment">// 自定义二分搜索树集合Set</span>
<span class="token keyword">class</span> <span class="token class-name">MyBinarySearchTreeSet</span> <span class="token punctuation">{</span>
    <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 借用二分搜索树来实现这个接口</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>myBinarySearchTree <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">MyBinarySearchTree</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 添加元素</span>
    <span class="token function">add</span><span class="token punctuation">(</span><span class="token parameter">element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>myBinarySearchTree<span class="token punctuation">.</span><span class="token function">add</span><span class="token punctuation">(</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 移除元素</span>
    <span class="token function">remove</span><span class="token punctuation">(</span><span class="token parameter">element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>myBinarySearchTree<span class="token punctuation">.</span><span class="token function">remove</span><span class="token punctuation">(</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 是否包含这个元素</span>
    <span class="token function">contains</span><span class="token punctuation">(</span><span class="token parameter">element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>myBinarySearchTree<span class="token punctuation">.</span><span class="token function">contains</span><span class="token punctuation">(</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 遍历操作</span>
    <span class="token comment">// 第一个参数 是回掉函数，</span>
    <span class="token comment">// 第二个参数 是遍历的方式 深度优先遍历(前pre、中in、后post)，广度优先遍历(层序level)</span>
    <span class="token function">each</span><span class="token punctuation">(</span><span class="token parameter">operator<span class="token punctuation">,</span> method</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 遍历方式默认是非递归的前序遍历，</span>
        <span class="token comment">// 其它的遍历方式就是递归的前、中、后、层序遍历。</span>
        <span class="token keyword">switch</span> <span class="token punctuation">(</span>method<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">case</span> <span class="token string">'pre'</span><span class="token operator">:</span>
            <span class="token keyword">this</span><span class="token punctuation">.</span>myBinarySearchTree<span class="token punctuation">.</span><span class="token function">preOrder</span><span class="token punctuation">(</span>operator<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">break</span><span class="token punctuation">;</span>
        <span class="token keyword">case</span> <span class="token string">'in'</span><span class="token operator">:</span>
            <span class="token keyword">this</span><span class="token punctuation">.</span>myBinarySearchTree<span class="token punctuation">.</span><span class="token function">inOrder</span><span class="token punctuation">(</span>operator<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">break</span><span class="token punctuation">;</span>
        <span class="token keyword">case</span> <span class="token string">'post'</span><span class="token operator">:</span>
            <span class="token keyword">this</span><span class="token punctuation">.</span>myBinarySearchTree<span class="token punctuation">.</span><span class="token function">postOrder</span><span class="token punctuation">(</span>operator<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">break</span><span class="token punctuation">;</span>
        <span class="token keyword">case</span> <span class="token string">'level'</span><span class="token operator">:</span>
            <span class="token keyword">this</span><span class="token punctuation">.</span>myBinarySearchTree<span class="token punctuation">.</span><span class="token function">levelOrder</span><span class="token punctuation">(</span>operator<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">break</span><span class="token punctuation">;</span>
        <span class="token keyword">default</span><span class="token operator">:</span>
            <span class="token keyword">this</span><span class="token punctuation">.</span>myBinarySearchTree<span class="token punctuation">.</span><span class="token function">nonRecursivePreOrder</span><span class="token punctuation">(</span>operator<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">break</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 获取集合中实际的元素个数</span>
    <span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>myBinarySearchTree<span class="token punctuation">.</span><span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 返回集合是否为空的bool值</span>
    <span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>myBinarySearchTree<span class="token punctuation">.</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><p><strong>Main</strong></p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token comment">// main 函数</span>
<span class="token keyword">class</span> <span class="token class-name">Main</span> <span class="token punctuation">{</span>
    <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">alterLine</span><span class="token punctuation">(</span><span class="token string">'MyBinarySearchTreeSet Area'</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">{</span>
        <span class="token keyword">let</span> n <span class="token operator">=</span> <span class="token number">5</span><span class="token punctuation">;</span>
        <span class="token keyword">let</span> set <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">MyBinarySearchTreeSet</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">let</span> random <span class="token operator">=</span> Math<span class="token punctuation">.</span>random<span class="token punctuation">;</span>
        <span class="token keyword">let</span> temp <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            temp <span class="token operator">=</span> <span class="token function">random</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
            set<span class="token punctuation">.</span><span class="token function">add</span><span class="token punctuation">(</span>n <span class="token operator">*</span> n <span class="token operator">*</span> n <span class="token operator">*</span> temp<span class="token punctuation">)</span><span class="token punctuation">;</span>
            set<span class="token punctuation">.</span><span class="token function">add</span><span class="token punctuation">(</span>n <span class="token operator">*</span> n <span class="token operator">*</span> n <span class="token operator">*</span> temp<span class="token punctuation">)</span><span class="token punctuation">;</span>
            set<span class="token punctuation">.</span><span class="token function">add</span><span class="token punctuation">(</span>n <span class="token operator">*</span> n <span class="token operator">*</span> n <span class="token operator">*</span> temp<span class="token punctuation">)</span><span class="token punctuation">;</span>
            set<span class="token punctuation">.</span><span class="token function">add</span><span class="token punctuation">(</span>n <span class="token operator">*</span> n <span class="token operator">*</span> n <span class="token operator">*</span> temp<span class="token punctuation">)</span><span class="token punctuation">;</span>
            set<span class="token punctuation">.</span><span class="token function">add</span><span class="token punctuation">(</span>n <span class="token operator">*</span> n <span class="token operator">*</span> n <span class="token operator">*</span> temp<span class="token punctuation">)</span><span class="token punctuation">;</span>
            set<span class="token punctuation">.</span><span class="token function">add</span><span class="token punctuation">(</span>n <span class="token operator">*</span> n <span class="token operator">*</span> n <span class="token operator">*</span> temp<span class="token punctuation">)</span><span class="token punctuation">;</span>
            set<span class="token punctuation">.</span><span class="token function">add</span><span class="token punctuation">(</span>n <span class="token operator">*</span> n <span class="token operator">*</span> n <span class="token operator">*</span> temp<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>set<span class="token punctuation">.</span><span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">show</span><span class="token punctuation">(</span>set<span class="token punctuation">.</span><span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">let</span> array <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">MyArray</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span>
        set<span class="token punctuation">.</span><span class="token function">each</span><span class="token punctuation">(</span><span class="token parameter">element</span> <span class="token operator">=&gt;</span> <span class="token punctuation">{</span>
            console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">show</span><span class="token punctuation">(</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>
            array<span class="token punctuation">.</span><span class="token function">add</span><span class="token punctuation">(</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> array<span class="token punctuation">.</span><span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            set<span class="token punctuation">.</span><span class="token function">remove</span><span class="token punctuation">(</span>array<span class="token punctuation">.</span><span class="token function">get</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>set<span class="token punctuation">.</span><span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">show</span><span class="token punctuation">(</span>set<span class="token punctuation">.</span><span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 将内容显示在页面上</span>
    <span class="token function">show</span><span class="token punctuation">(</span><span class="token parameter">content</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        document<span class="token punctuation">.</span>body<span class="token punctuation">.</span>innerHTML <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>content<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">&lt;br /&gt;&lt;br /&gt;</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 展示分割线</span>
    <span class="token function">alterLine</span><span class="token punctuation">(</span><span class="token parameter">title</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> line <span class="token operator">=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token string">--------------------</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>title<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">----------------------</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
        console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>line<span class="token punctuation">)</span><span class="token punctuation">;</span>
        document<span class="token punctuation">.</span>body<span class="token punctuation">.</span>innerHTML <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>line<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">&lt;br /&gt;&lt;br /&gt;</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

<span class="token comment">// 页面加载完毕</span>
window<span class="token punctuation">.</span><span class="token function-variable function">onload</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token comment">// 执行主函数</span>
    <span class="token keyword">new</span> <span class="token class-name">Main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre></div><h2 id="集合-基于链表的实现"><a href="#集合-基于链表的实现" class="header-anchor">#</a> 集合-基于链表的实现</h2> <p>集合设计的是一个接口，所以可以采用不同的底层数据结构来进行实现它，和栈和队列一样，可以使用底层的数据结构动态数组和链表来实现它，那么也可以通过链表来实现集合。</p> <p>二分搜索树和链表都属于动态数据结构，对于二分搜索树来说数据都是存储在一个一个 node 中，链表也是把数据存储到一个一个的 node 中。不过这两个 node 的定义是不同的，对于二分搜索树来说有左右两个指针来指向左子树和右子树，而对于链表来说每一个 node 都指向了下一个 node。<br>
由于它们同样是动态数据结构，所以可以基于这两种数据结构为底层实现这个集合，还可以相应的进行比较这两种数据结构实现后的性能，通过它们的性能比较可以看出二分搜索树这种数据结构的优势所在。</p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token comment">// 二分搜索树的Node</span>
<span class="token keyword">class</span> <span class="token class-name">Node</span> <span class="token punctuation">{</span>
    e<span class="token punctuation">;</span> <span class="token comment">// Element</span>
    left<span class="token punctuation">;</span> <span class="token comment">// Node</span>
    right<span class="token punctuation">;</span> <span class="token comment">// Node</span>
<span class="token punctuation">}</span>

<span class="token comment">// 链表的Node</span>
<span class="token keyword">class</span> <span class="token class-name">Node</span> <span class="token punctuation">{</span>
    e<span class="token punctuation">;</span> <span class="token comment">// Element</span>
    next<span class="token punctuation">;</span> <span class="token comment">// Node</span>
<span class="token punctuation">}</span>
</code></pre></div><h3 id="集合接口-2"><a href="#集合接口-2" class="header-anchor">#</a> 集合接口</h3> <p><code>MySet</code></p> <p><code>void add (e)</code> : 不能添加重复元素<br> <code>void remove (e)</code><br> <code>boolean conatains (e)</code><br> <code>int getSize ()</code><br> <code>boolean isEmpty ()</code></p> <p>使用 MyLinkedListSet 来实现这个集合的接口</p> <h3 id="代码示例-2"><a href="#代码示例-2" class="header-anchor">#</a> 代码示例</h3> <p><code>( class: MyLinkedList, class: MyLinkedListSet)</code></p> <p><strong>MyLinkedList</strong></p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token comment">// 自定义链表节点</span>
<span class="token keyword">class</span> <span class="token class-name">MyLinkedListNode</span> <span class="token punctuation">{</span>
    <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token parameter">element <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">,</span> next <span class="token operator">=</span> <span class="token keyword">null</span></span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>element <span class="token operator">=</span> element<span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>next <span class="token operator">=</span> next<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 将一个数组对象 转换为一个链表 并且追加到当前节点上</span>
    <span class="token function">appendToLinkedListNode</span><span class="token punctuation">(</span><span class="token parameter">array</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> head <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>element <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 头部添加</span>
        head <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">;</span>
        head<span class="token punctuation">.</span>element <span class="token operator">=</span> array<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
        head<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
        <span class="token comment">// 插入式</span>
        head <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">MyLinkedListNode</span><span class="token punctuation">(</span>array<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        head<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>next <span class="token operator">=</span> head<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 添加节点的方式  头部添加、尾部添加、中间插入</span>

        <span class="token comment">// 尾部添加节点的方式</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> array<span class="token punctuation">.</span>length<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        head<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">MyLinkedListNode</span><span class="token punctuation">(</span>array<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        head <span class="token operator">=</span> head<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token comment">//@override</span>
    <span class="token comment">// toString 2018-10-20-jwl</span>
    <span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>element<span class="token punctuation">.</span><span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

<span class="token comment">// 自定义链表</span>
<span class="token keyword">class</span> <span class="token class-name">MyLinkedList</span> <span class="token punctuation">{</span>
    <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>dummyHead <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">MyLinkedListNode</span><span class="token punctuation">(</span><span class="token keyword">null</span><span class="token punctuation">,</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>size <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 获取链表中实际的节点个数</span>
    <span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 判断链表是否为空</span>
    <span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>size <span class="token operator">===</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 在链表头添加节点</span>
    <span class="token function">addFirst</span><span class="token punctuation">(</span><span class="token parameter">element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// let node = new MyLinkedListNode(element, null);</span>
        <span class="token comment">// node.next = this.head;</span>
        <span class="token comment">// this.head = node;</span>
        <span class="token comment">// this.size ++;</span>

        <span class="token comment">// 改用虚拟头节点</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">insert</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> element<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 在链表指定索引处插入节点</span>
    <span class="token function">insert</span><span class="token punctuation">(</span><span class="token parameter">index<span class="token punctuation">,</span> element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>index <span class="token operator">&lt;</span> <span class="token number">0</span> <span class="token operator">||</span> index <span class="token operator">&gt;</span> <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">Error</span><span class="token punctuation">(</span><span class="token string">'add error. index &lt; 0 or index &gt; size'</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 第一个prev就是dummyHead</span>
        <span class="token keyword">let</span> prev <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>dummyHead<span class="token punctuation">;</span>
        <span class="token comment">// 之前变量i(索引)之所以要从 1 开始，因为索引为0的那个节点就是head，循环就不需要从0开始了，</span>
        <span class="token comment">// 现在索引之所以要从 0 开始， 因为初始化时 多增加了一个虚拟的头节点</span>
        <span class="token comment">// （因为这个索引为0的节点并不是dummyHead，dummyHead这个节点并不记录为链表中的实际节点），</span>
        <span class="token comment">// 小于index是因为要找到指定索引位置的前一个节点</span>
        <span class="token comment">// 循环是因为 要继续找到指定索引处的节点的前一个节点</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> index<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 不停的切换引用，直到找到对应索引处节点的下一个节点</span>
        prev <span class="token operator">=</span> prev<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">MyLinkedListNode</span><span class="token punctuation">(</span>element<span class="token punctuation">,</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        node<span class="token punctuation">.</span>next <span class="token operator">=</span> prev<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        prev<span class="token punctuation">.</span>next <span class="token operator">=</span> node<span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token operator">++</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 扩展：在链表最后一个节点的位置添加节点</span>
    <span class="token function">addLast</span><span class="token punctuation">(</span><span class="token parameter">element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">insert</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token punctuation">,</span> element<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 获取指定索引位置的元素</span>
    <span class="token function">get</span><span class="token punctuation">(</span>index<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 判断索引合法性</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>index <span class="token operator">&lt;</span> <span class="token number">0</span> <span class="token operator">||</span> index <span class="token operator">&gt;=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">Error</span><span class="token punctuation">(</span><span class="token string">'get error. index &lt; 0 or index &gt;= size'</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 如果你要找指定索引节点的前一个节点 就使用dummyHead</span>
        <span class="token comment">// 如果你要找到指定索引节点 就使用dummyHead.next</span>
        <span class="token comment">// 因为duumyHead并不是第一个节点，因为它是一个虚拟节点，</span>
        <span class="token comment">// dummyHead.next才是真正被记录的第一个节点。</span>
        <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>dummyHead<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> index<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        node <span class="token operator">=</span> node<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">return</span> node<span class="token punctuation">.</span>element<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 获取头节点的元素</span>
    <span class="token function">getFirst</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">get</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 获取尾节点的元素</span>
    <span class="token function">getLast</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">get</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>size <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 设置指定索引位置的元素值</span>
    <span class="token function">set</span><span class="token punctuation">(</span>index<span class="token punctuation">,</span> element<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 判断索引合法性</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>index <span class="token operator">&lt;</span> <span class="token number">0</span> <span class="token operator">||</span> index <span class="token operator">&gt;=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">Error</span><span class="token punctuation">(</span><span class="token string">'get error. index &lt; 0 or index &gt;= size'</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 从第一个真正被记录的节点开始，从0开始</span>
        <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>dummyHead<span class="token punctuation">.</span>next<span class="token punctuation">;</span>

        <span class="token comment">// 索引为 0 时，实际上切换到的节点 它的索引为 1</span>
        <span class="token comment">// i &lt; index ，当索引为 index-1 时， 实际上切换到的节点 它的索引为index</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> index<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 每一次切换 都只是改变引用</span>
        <span class="token comment">// 不的在链表中找下一个节点</span>
        node <span class="token operator">=</span> node<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        node<span class="token punctuation">.</span>element <span class="token operator">=</span> element<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 所有节点中是否有包含该元素</span>
    <span class="token function">contains</span><span class="token punctuation">(</span><span class="token parameter">element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>dummyHead<span class="token punctuation">;</span>

        <span class="token keyword">while</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>next <span class="token operator">!==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>next<span class="token punctuation">.</span>element <span class="token operator">===</span> element<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
        <span class="token comment">// 不停的向下切换</span>
        node <span class="token operator">=</span> node<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 删除指定索引位置的节点</span>
    <span class="token function">remove</span><span class="token punctuation">(</span><span class="token parameter">index</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 验证索引的合法性</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>index <span class="token operator">&lt;</span> <span class="token number">0</span> <span class="token operator">||</span> index <span class="token operator">&gt;=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">Error</span><span class="token punctuation">(</span><span class="token string">'remove error. index &lt; 0 or index &gt; this.size'</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>dummyHead<span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> index<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        node <span class="token operator">=</span> node<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 待删除的节点</span>
        <span class="token keyword">let</span> delNode <span class="token operator">=</span> node<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token comment">// 给待删除那个节点的前一个的节点的next引用替换为</span>
        <span class="token comment">// 但删除的这个节点的next</span>
        node<span class="token punctuation">.</span>next <span class="token operator">=</span> delNode<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token comment">// 或者这样也行</span>
        <span class="token comment">// node.next = node.next.next;</span>

        <span class="token comment">// 临时存储待删除的那个节点里的元素</span>
        <span class="token keyword">let</span> element <span class="token operator">=</span> delNode<span class="token punctuation">.</span>element<span class="token punctuation">;</span>
        <span class="token comment">// 清空 待删除的节点</span>
        delNode <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token operator">--</span><span class="token punctuation">;</span>

        <span class="token keyword">return</span> element<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 扩展：移除链表头的元素</span>
    <span class="token function">removeFirst</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">remove</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 扩展：移除链表尾部的元素</span>
    <span class="token function">removeLast</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">remove</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>size <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 输出链表中的信息</span>
    <span class="token comment">// @Override toString 2018-10-21-jwl</span>
    <span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> arrInfo <span class="token operator">=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token string">LinkedList: size = </span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span><span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">，\n</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
        arrInfo <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token string">data = front  [</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
        <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>dummyHead<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>next <span class="token operator">!==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        arrInfo <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>node<span class="token punctuation">.</span>element<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">-&gt;</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
        node <span class="token operator">=</span> node<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        arrInfo <span class="token operator">+=</span> <span class="token string">'NULL] tail'</span><span class="token punctuation">;</span>

        <span class="token comment">// 在页面上展示</span>
        document<span class="token punctuation">.</span>body<span class="token punctuation">.</span>innerHTML <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>arrInfo<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">&lt;br /&gt;&lt;br /&gt; </span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>

        <span class="token keyword">return</span> arrInfo<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><p><strong>MyLinkedListSet</strong></p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token comment">// 自定义链表集合Set</span>
<span class="token keyword">class</span> <span class="token class-name">MyLinkedListSet</span> <span class="token punctuation">{</span>
    <span class="token comment">//</span>
    <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>myLinkedList <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">MyLinkedList</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token function">add</span><span class="token punctuation">(</span><span class="token parameter">element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span><span class="token keyword">this</span><span class="token punctuation">.</span>myLinkedList<span class="token punctuation">.</span><span class="token function">contains</span><span class="token punctuation">(</span>element<span class="token punctuation">)</span><span class="token punctuation">)</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>myLinkedList<span class="token punctuation">.</span><span class="token function">addFirst</span><span class="token punctuation">(</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token function">remove</span><span class="token punctuation">(</span><span class="token parameter">element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>myLinkedList<span class="token punctuation">.</span><span class="token function">removeElement</span><span class="token punctuation">(</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token function">contains</span><span class="token punctuation">(</span><span class="token parameter">element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>myLinkedList<span class="token punctuation">.</span><span class="token function">contains</span><span class="token punctuation">(</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token function">each</span><span class="token punctuation">(</span><span class="token parameter">operator</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> size <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>myLinkedList<span class="token punctuation">.</span><span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> size<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token function">operator</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>myLinkedList<span class="token punctuation">.</span><span class="token function">get</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>myLinkedList<span class="token punctuation">.</span><span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>myLinkedList<span class="token punctuation">.</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><h2 id="集合类的复杂度分析"><a href="#集合类的复杂度分析" class="header-anchor">#</a> 集合类的复杂度分析</h2> <p>实现了两个基于动态数据结构的集合类，分别是基于二分搜索树的集合类 MyBSTSet和基于链表的集合类 MyLinkedListSet，基于链表的集合类性能要差一些。</p> <p>对集合的时间复杂度分析，分别是增加 add、查询 contains、删除 remove</p> <h3 id="mylinkedlistset-与-mybstset-时间复杂度对比"><a href="#mylinkedlistset-与-mybstset-时间复杂度对比" class="header-anchor">#</a> MyLinkedListSet 与 MyBSTSet 时间复杂度对比</h3> <p>MyLinkedListSet 的时间复杂度为<code>O(n)</code>，MyBSTSet 的时间复杂度为<code>O(h) or O(log n)</code>，<code>h = log2 (n+1) = O(log2 n)</code>，h 和 n 之间成一个 log 关系，log 以 2 为底的(n+1)。<br>
通常称它们之间的关系为<code>O(log2 n)</code>也就是大 O log 以 2 为底 n 这样的一个关系，在大 O 这样的一个定义下，这个底的大小可以忽略不计，因为认为常数不重要，以 2 为底、以 10 为底、以 100 为底，它都是一个 log 级别的函数。<br>
就像看线性关系，前面的系数也是不关注的，它是<code>1*n、2*n、100*n、10000*n</code>，它们都是线性的一个关系，所以这个关系可以写成<code>O(log n)</code>。</p> <h3 id="二分搜索树的局限性"><a href="#二分搜索树的局限性" class="header-anchor">#</a> 二分搜索树的局限性</h3> <p>虽然二分搜索树实现的集合时间复杂度为<code>O(log n)</code>，但是计算出这个时间复杂度是在满二叉树的情况下，所以这个<code>O(log n)</code>其实是一个最优的情况，如果二叉树稍微有一些倾斜，也能达到<code>O(log n)</code>这个级别。但是自己实现的二分搜索树有一个致命的问题，它有最坏的情况，对于同样的数据，可以创建出不同的二分搜索树。<br>
例如每一个节点的左孩子都为空只有右孩子，在这种情况下二分搜索树和一个链表是一样的，也就是说这棵二分搜索树的高度等于节点数，这就是二分搜索树最坏的情况，例如按照顺序添加<code>[1,2,3,4,5,6]</code>，就可以创建出一颗退化成链表的二分搜索树。<br>
在大多数实际情况下 MyBSTSet 不会那么奇怪的按照顺序添加数据，因为那样会让二分搜索树退化成链表，但是也有可能你的二分搜索树就会遇到最差的情况或者接近最差的情况，那么此时你二分搜索树的性能近乎接近链表的性能，这样的性能其实也是<code>O(n)</code>这样的性能，这也是你之前实现的二分搜索树的局限性。<br>
但是平均来讲，大多数情况下它都能达到<code>O(log n)</code>的时间复杂度，但是依然会有特殊情况，最差的情况他会退化成和链表一样的<code>O(n)</code>，所以就需要解决这个问题，解决这个问题的方式就是创建所谓的平衡二叉树。<br>
所以非常准确的说二分搜索树的时间复杂度为<code>O(h)</code>，在大多数情况下这个 h 等于<code>log n</code>，如果非常的不巧，那么这个 h 等于 n。</p> <h3 id="log-n-和-n-的差距"><a href="#log-n-和-n-的差距" class="header-anchor">#</a> log n 和 n 的差距</h3> <p>当<code>n=16</code>的时候，logn 让它取 2 为底，相应的<code>log2 n</code>的值为 4，n 的值就是 16。也就是说它们相差四倍，随着 n 的增大，它们之间的差距就会越来越大。<br>
比如说<code>n=1024</code>的时候，logn 还是让它取 2 为底，因为 2 的十次方为 1024，那么相应的<code>log2 n</code>的值为 10，n 的值就是 1024，在这种情况下，二者之间相差一百倍。如果<code>n=100万</code>这个级别的数据的话，logn 还是让它取 2 为底，因为 2 的 20 次方大概就是 100 万，那么相应的<code>log2 n</code>的值为 20，n 的值就是 100 万，在这种情况下，二者之间<strong>相差 5 万倍</strong>。</p> <p>它们之间的差距非常非常大。  比如你使用<code>O(log n)</code>这个算法和<code>O(n)</code>这个算法，输入的数据为 100 万个，如果你<code>O(log n)</code>这个算法花一秒时间就跑完的话，那么<code>O(n)</code>这个算法就需要花 5 万秒，大概 14 个小时。<br>
再比如你<code>O(log n)</code>这个算法要花一天的时间跑完这个程序，那么<code>O(n)</code>这个算法就需要花 5 万天，大概 137 年的事件才能跑出结果。这概念就像你睡一觉 24 小时后<code>O(log n)</code>算法的程序就跑出结果了，而<code>O(n)</code>算法的程序你这一辈子都跑不出结果来。</p> <p>log n 这个复杂度是非常快非常快的一个时间复杂度，很多高级的排序算法最终它是 nlogn 这个时间复杂度，这个时间复杂度比 n 方的时间复杂度快了非常多倍，快的倍数与<code>O(log n)</code>和<code>O(n)</code>差不多，虽然它们之间还有常数的差异，但是在复杂度分析的时不去管这个常数的差异。</p> <h3 id="mylinkedlistset"><a href="#mylinkedlistset" class="header-anchor">#</a> MyLinkedListSet</h3> <p>增加 add <code>O(n)</code>：  为了防止元素重复，所以必须先查询一遍，然后再决定添加不添加，虽然添加的复杂度为<code>O(1)</code>，但是查询的操作是遍历整个链表，所以整体时间复杂度为<code>O(n)</code>。</p> <p>查询 contains <code>O(n)</code>：查询的操作是遍历整个链表，所以时间复杂度为<code>O(n)</code></p> <p>删除 remove <code>O(n)</code>：删操作也需要遍历整个链表，所以时间复杂度为<code>O(n)</code></p> <h3 id="mybstset"><a href="#mybstset" class="header-anchor">#</a> MyBSTSet</h3> <p>增加 add <code>O(h) or O(log n)</code>：添加一个元素，待添加的这个元素和根节点的这个元素进行比较，如果小于的话直接去左子树，如果大于的话直接去右子树，每一次近乎都能把一半儿的元素给扔掉。<br>
添加这个元素这个过程其实就像是在走一个链表，一层一层的从这个树的根节点向叶子节点出发，最终一共经历的节点个数就是这棵树的<code>高度</code>，也就是整棵树最大的深度。<br>
查询元素也是如此，删除元素还是如此，所以对于二分搜索树来说，这三个时间复杂度都是<code>O(h)</code>这个级别的，这个 h 就是二分搜索树的高度。</p> <p>查询 contains <code>O(h) or O(log n)</code></p> <p>删除 remove <code>O(h) or O(log n)</code></p> <h3 id="二分搜索树"><a href="#二分搜索树" class="header-anchor">#</a> 二分搜索树</h3> <p><strong>满的二叉树每一层有多少个节点</strong><br>
第 0 层：1 个节点<br>
第 1 层：2 个节点<br>
第 2 层：4 个节点<br>
第 3 层：8 个节点<br>
第 4 层：16 个节点<br>
第 h-1 层：2^(h-1)个节点</p> <p><strong>满的二叉树一共有多少个节点</strong>？</p> <p>可以通过等比数列来进行计算，<code>2^(1-1) + 2^(2-1) + ... + 2^(h-1)``= 1 x (1-2^(h)) / (1-2) = 2^(h) - 1 = n</code>。</p> <p><strong>满的二叉树的高度与节点个数之间的关系</strong></p> <p><code>h = log2 (n+1) = O(log2 n)</code>，h 和 n 之间成一个 log 关系，log 以 2 为底的(n+1)，通常称它们之间的关系为<code>O(log2 n)</code>，也就是大 O log 以 2 为底 n 这样的一个关系，在大 O 这样的一个定义下，这个底的大小可以忽略不计。<br>
因为认为常数不重要，以 2 为底、以 10 为底、以 100 为底，它都是一个 log 级别的函数，就像看线性关系，前面的系数也是不关注的，它是<code>1*n、2*n、100*n、10000*n</code>，它们都是线性的一个关系，所以这个关系可以写成<code>O(log n)</code>。</p> <p>二分搜索树这种底层的数据结构实现的集合，它性能是大大的快于链表实现的集合。</p> <h3 id="代码示例-3"><a href="#代码示例-3" class="header-anchor">#</a> 代码示例</h3> <p><code>(class: MyLinkedList, class: MyBinarySearchTree, class: PerformanceTest,</code><br> <code>class: MyLinkedListSet, class:MyBSTSet , class: Main)</code></p> <p><strong>MyLinkedList</strong></p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token comment">// 自定义链表节点</span>
<span class="token keyword">class</span> <span class="token class-name">MyLinkedListNode</span> <span class="token punctuation">{</span>
    <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token parameter">element <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">,</span> next <span class="token operator">=</span> <span class="token keyword">null</span></span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>element <span class="token operator">=</span> element<span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>next <span class="token operator">=</span> next<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 将一个数组对象 转换为一个链表 并且追加到当前节点上</span>
    <span class="token function">appendToLinkedListNode</span><span class="token punctuation">(</span><span class="token parameter">array</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> head <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>element <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 头部添加</span>
        head <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">;</span>
        head<span class="token punctuation">.</span>element <span class="token operator">=</span> array<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
        head<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
        <span class="token comment">// 插入式</span>
        head <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">MyLinkedListNode</span><span class="token punctuation">(</span>array<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        head<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>next <span class="token operator">=</span> head<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 添加节点的方式  头部添加、尾部添加、中间插入</span>

        <span class="token comment">// 尾部添加节点的方式</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> array<span class="token punctuation">.</span>length<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        head<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">MyLinkedListNode</span><span class="token punctuation">(</span>array<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        head <span class="token operator">=</span> head<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token comment">//@override</span>
    <span class="token comment">// toString 2018-10-20-jwl</span>
    <span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>element<span class="token punctuation">.</span><span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

<span class="token comment">// 自定义链表</span>
<span class="token keyword">class</span> <span class="token class-name">MyLinkedList</span> <span class="token punctuation">{</span>
    <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>dummyHead <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">MyLinkedListNode</span><span class="token punctuation">(</span><span class="token keyword">null</span><span class="token punctuation">,</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>size <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 获取链表中实际的节点个数</span>
    <span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 判断链表是否为空</span>
    <span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>size <span class="token operator">===</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 在链表头添加节点</span>
    <span class="token function">addFirst</span><span class="token punctuation">(</span><span class="token parameter">element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// let node = new MyLinkedListNode(element, null);</span>
        <span class="token comment">// node.next = this.head;</span>
        <span class="token comment">// this.head = node;</span>
        <span class="token comment">// this.size ++;</span>

        <span class="token comment">// 改用虚拟头节点</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">insert</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> element<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 在链表指定索引处插入节点</span>
    <span class="token function">insert</span><span class="token punctuation">(</span><span class="token parameter">index<span class="token punctuation">,</span> element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>index <span class="token operator">&lt;</span> <span class="token number">0</span> <span class="token operator">||</span> index <span class="token operator">&gt;</span> <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">Error</span><span class="token punctuation">(</span><span class="token string">'add error. index &lt; 0 or index &gt; size'</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 第一个prev就是dummyHead</span>
        <span class="token keyword">let</span> prev <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>dummyHead<span class="token punctuation">;</span>
        <span class="token comment">// 之前变量i(索引)之所以要从 1 开始，因为索引为0的那个节点就是head，循环就不需要从0开始了，</span>
        <span class="token comment">// 现在索引之所以要从 0 开始， 因为初始化时 多增加了一个虚拟的头节点</span>
        <span class="token comment">// （因为这个索引为0的节点并不是dummyHead，dummyHead这个节点并不记录为链表中的实际节点），</span>
        <span class="token comment">// 小于index是因为要找到指定索引位置的前一个节点</span>
        <span class="token comment">// 循环是因为 要继续找到指定索引处的节点的前一个节点</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> index<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 不停的切换引用，直到找到对应索引处节点的下一个节点</span>
        prev <span class="token operator">=</span> prev<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">MyLinkedListNode</span><span class="token punctuation">(</span>element<span class="token punctuation">,</span> <span class="token keyword">null</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        node<span class="token punctuation">.</span>next <span class="token operator">=</span> prev<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        prev<span class="token punctuation">.</span>next <span class="token operator">=</span> node<span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token operator">++</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 扩展：在链表最后一个节点的位置添加节点</span>
    <span class="token function">addLast</span><span class="token punctuation">(</span><span class="token parameter">element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">insert</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token punctuation">,</span> element<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 获取指定索引位置的元素</span>
    <span class="token function">get</span><span class="token punctuation">(</span>index<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 判断索引合法性</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>index <span class="token operator">&lt;</span> <span class="token number">0</span> <span class="token operator">||</span> index <span class="token operator">&gt;=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">Error</span><span class="token punctuation">(</span><span class="token string">'get error. index &lt; 0 or index &gt;= size'</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 如果你要找指定索引节点的前一个节点 就使用dummyHead</span>
        <span class="token comment">// 如果你要找到指定索引节点 就使用dummyHead.next</span>
        <span class="token comment">// 因为duumyHead并不是第一个节点，因为它是一个虚拟节点，</span>
        <span class="token comment">// dummyHead.next才是真正被记录的第一个节点。</span>
        <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>dummyHead<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> index<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        node <span class="token operator">=</span> node<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">return</span> node<span class="token punctuation">.</span>element<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 获取头节点的元素</span>
    <span class="token function">getFirst</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">get</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 获取尾节点的元素</span>
    <span class="token function">getLast</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">get</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>size <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 设置指定索引位置的元素值</span>
    <span class="token function">set</span><span class="token punctuation">(</span>index<span class="token punctuation">,</span> element<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 判断索引合法性</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>index <span class="token operator">&lt;</span> <span class="token number">0</span> <span class="token operator">||</span> index <span class="token operator">&gt;=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">Error</span><span class="token punctuation">(</span><span class="token string">'get error. index &lt; 0 or index &gt;= size'</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 从第一个真正被记录的节点开始，从0开始</span>
        <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>dummyHead<span class="token punctuation">.</span>next<span class="token punctuation">;</span>

        <span class="token comment">// 索引为 0 时，实际上切换到的节点 它的索引为 1</span>
        <span class="token comment">// i &lt; index ，当索引为 index-1 时， 实际上切换到的节点 它的索引为index</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> index<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 每一次切换 都只是改变引用</span>
        <span class="token comment">// 不的在链表中找下一个节点</span>
        node <span class="token operator">=</span> node<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        node<span class="token punctuation">.</span>element <span class="token operator">=</span> element<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 所有节点中是否有包含该元素</span>
    <span class="token function">contains</span><span class="token punctuation">(</span><span class="token parameter">element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>dummyHead<span class="token punctuation">;</span>

        <span class="token keyword">while</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>next <span class="token operator">!==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>next<span class="token punctuation">.</span>element <span class="token operator">===</span> element<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
        <span class="token comment">// 不停的向下切换</span>
        node <span class="token operator">=</span> node<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 删除指定索引位置的节点</span>
    <span class="token function">remove</span><span class="token punctuation">(</span><span class="token parameter">index</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 验证索引的合法性</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>index <span class="token operator">&lt;</span> <span class="token number">0</span> <span class="token operator">||</span> index <span class="token operator">&gt;=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">Error</span><span class="token punctuation">(</span><span class="token string">'remove error. index &lt; 0 or index &gt; this.size'</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>dummyHead<span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> index<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        node <span class="token operator">=</span> node<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 待删除的节点</span>
        <span class="token keyword">let</span> delNode <span class="token operator">=</span> node<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token comment">// 给待删除那个节点的前一个的节点的next引用替换为</span>
        <span class="token comment">// 但删除的这个节点的next</span>
        node<span class="token punctuation">.</span>next <span class="token operator">=</span> delNode<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token comment">// 或者这样也行</span>
        <span class="token comment">// node.next = node.next.next;</span>

        <span class="token comment">// 临时存储待删除的那个节点里的元素</span>
        <span class="token keyword">let</span> element <span class="token operator">=</span> delNode<span class="token punctuation">.</span>element<span class="token punctuation">;</span>
        <span class="token comment">// 清空 待删除的节点</span>
        delNode <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token operator">--</span><span class="token punctuation">;</span>

        <span class="token keyword">return</span> element<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 扩展：移除链表头的元素</span>
    <span class="token function">removeFirst</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">remove</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 扩展：移除链表尾部的元素</span>
    <span class="token function">removeLast</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">remove</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>size <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 新增：根据元素来删除链表中的元素 2018-11-05</span>
    <span class="token function">removeElement</span><span class="token punctuation">(</span><span class="token parameter">element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> prev <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>dummyHead<span class="token punctuation">;</span>

        <span class="token keyword">while</span> <span class="token punctuation">(</span>prev<span class="token punctuation">.</span>next <span class="token operator">!==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>prev<span class="token punctuation">.</span>next<span class="token punctuation">.</span>element <span class="token operator">===</span> element<span class="token punctuation">)</span> <span class="token keyword">break</span><span class="token punctuation">;</span>
        prev <span class="token operator">=</span> prev<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">if</span> <span class="token punctuation">(</span>prev<span class="token punctuation">.</span>next <span class="token operator">!==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> delNode <span class="token operator">=</span> prev<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        prev<span class="token punctuation">.</span>next <span class="token operator">=</span> delNode<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        delNode <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token operator">--</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 输出链表中的信息</span>
    <span class="token comment">// @Override toString 2018-10-21-jwl</span>
    <span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> arrInfo <span class="token operator">=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token string">LinkedList: size = </span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span><span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">，\n</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
        arrInfo <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token string">data = front  [</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
        <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>dummyHead<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>next <span class="token operator">!==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        arrInfo <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>node<span class="token punctuation">.</span>element<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">-&gt;</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
        node <span class="token operator">=</span> node<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        arrInfo <span class="token operator">+=</span> <span class="token string">'NULL] tail'</span><span class="token punctuation">;</span>

        <span class="token comment">// 在页面上展示</span>
        document<span class="token punctuation">.</span>body<span class="token punctuation">.</span>innerHTML <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>arrInfo<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">&lt;br /&gt;&lt;br /&gt; </span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>

        <span class="token keyword">return</span> arrInfo<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><p><strong>MyBinarySearchTree</strong></p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token comment">// 自定义二分搜索树节点</span>
<span class="token keyword">class</span> <span class="token class-name">MyBinarySearchTreeNode</span> <span class="token punctuation">{</span>
    <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token parameter">element<span class="token punctuation">,</span> left <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">,</span> right <span class="token operator">=</span> <span class="token keyword">null</span></span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 实际存储的元素</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>element <span class="token operator">=</span> element<span class="token punctuation">;</span>
        <span class="token comment">// 当前节点的左子树</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>left <span class="token operator">=</span> left<span class="token punctuation">;</span>
        <span class="token comment">// 当前节点的右子树</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>right <span class="token operator">=</span> right<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

<span class="token comment">// 自定义二分搜索树</span>
<span class="token keyword">class</span> <span class="token class-name">MyBinarySearchTree</span> <span class="token punctuation">{</span>
    <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>root <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>size <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 添加元素到二分搜索树中 +</span>
    <span class="token function">add</span><span class="token punctuation">(</span><span class="token parameter">element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>element <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">Error</span><span class="token punctuation">(</span><span class="token string">&quot;element is null. can't store.&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">this</span><span class="token punctuation">.</span>root <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveAdd</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">,</span> element<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 添加元素到二分搜索树中  递归算法 -</span>
    <span class="token function">recursiveAdd</span><span class="token punctuation">(</span><span class="token parameter">node<span class="token punctuation">,</span> newElement</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 解决最基本的问题 也就是递归函数调用的终止条件</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token operator">++</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> <span class="token keyword">new</span> <span class="token class-name">MyBinarySearchTreeNode</span><span class="token punctuation">(</span>newElement<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 1. 当前节点的元素比新元素大</span>
        <span class="token comment">// 那么新元素就会被添加到当前节点的左子树去</span>
        <span class="token comment">// 2. 当前节点的元素比新元素小</span>
        <span class="token comment">// 那么新元素就会被添加到当前节点的右子树去</span>
        <span class="token comment">// 3. 当前节点的元素比新元素相等</span>
        <span class="token comment">// 什么都不做了，因为目前不添加重复的元素</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">compare</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">,</span> newElement<span class="token punctuation">)</span> <span class="token operator">&gt;</span> <span class="token number">0</span><span class="token punctuation">)</span>
        node<span class="token punctuation">.</span>left <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveAdd</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>left<span class="token punctuation">,</span> newElement<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">compare</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">,</span> newElement<span class="token punctuation">)</span> <span class="token operator">&lt;</span> <span class="token number">0</span><span class="token punctuation">)</span>
        node<span class="token punctuation">.</span>right <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveAdd</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">,</span> newElement<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">else</span> <span class="token punctuation">{</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 将复杂问题分解成多个性质相同的小问题，</span>
        <span class="token comment">// 然后求出小问题的答案，</span>
        <span class="token comment">// 最终构建出原问题的答案</span>
        <span class="token keyword">return</span> node<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 判断二分搜索树中是否包含某个元素 +</span>
    <span class="token function">contains</span><span class="token punctuation">(</span><span class="token parameter">element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">Error</span><span class="token punctuation">(</span><span class="token string">&quot;root is null. can't query.&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveContains</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">,</span> element<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 判断二分搜索树种是否包含某个元素 递归算法 -</span>
    <span class="token function">recursiveContains</span><span class="token punctuation">(</span><span class="token parameter">node<span class="token punctuation">,</span> element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span>

        <span class="token comment">// 当前节点元素比 要搜索的元素 大</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">compare</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">,</span> element<span class="token punctuation">)</span> <span class="token operator">&gt;</span> <span class="token number">0</span><span class="token punctuation">)</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveContains</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>left<span class="token punctuation">,</span> element<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">compare</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">,</span> element<span class="token punctuation">)</span> <span class="token operator">&lt;</span> <span class="token number">0</span><span class="token punctuation">)</span>
        <span class="token comment">// 当前元素比 要搜索的元素 小</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveContains</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">,</span> element<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment">// 两个元素相等</span>
        <span class="token keyword">else</span> <span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 找到二分搜索树中的最大值的元素 +</span>
    <span class="token function">maximum</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>size <span class="token operator">===</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">Error</span><span class="token punctuation">(</span><span class="token string">'binary search tree is empty.'</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveMaximum</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">)</span><span class="token punctuation">.</span>element<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 找到二分搜索树中的最大值的元素的节点 递归算法 -</span>
    <span class="token function">recursiveMaximum</span><span class="token punctuation">(</span><span class="token parameter">node</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 解决最基本的问题  向右走再也走不动了，说明当前节点就是最大值节点。</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>right <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span> node<span class="token punctuation">;</span>

        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveMaximum</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 删除二分搜索树中最大值的元素的节点，并返回这个节点的元素 +</span>
    <span class="token function">removeMax</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> maxElement <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">maximum</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>root <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveRemoveMax</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> maxElement<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 删除二分搜索树中最大值的元素的节点，并返回这个节点 递归算法 -</span>
    <span class="token function">recursiveRemoveMax</span><span class="token punctuation">(</span><span class="token parameter">node</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>right <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 先存 当前这个节点的左子树，</span>
        <span class="token comment">// 因为可能当前这个节点仅仅没有右子树，只有左子树，</span>
        <span class="token comment">// 那么左子树可以替代当前这个节点。</span>
        <span class="token keyword">let</span> leftNode <span class="token operator">=</span> node<span class="token punctuation">.</span>left<span class="token punctuation">;</span>
        node<span class="token punctuation">.</span>left <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token operator">--</span><span class="token punctuation">;</span>

        <span class="token keyword">return</span> leftNode<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        node<span class="token punctuation">.</span>right <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveRemoveMax</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> node<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 找到二分搜索树中的最小值 +</span>
    <span class="token function">minimum</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>size <span class="token operator">===</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">Error</span><span class="token punctuation">(</span><span class="token string">'binary search tree is empty.'</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveMinimum</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">)</span><span class="token punctuation">.</span>element<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 找到二分搜索树中的最小值的元素的节点 递归算法 -</span>
    <span class="token function">recursiveMinimum</span><span class="token punctuation">(</span><span class="token parameter">node</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>left <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span> node<span class="token punctuation">;</span>

        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveMinimum</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>left<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 删除二分搜索树中最小值的元素的节点，并返回这个节点的元素 +</span>
    <span class="token function">removeMin</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> leftNode <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">minimum</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>root <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveRemoveMin</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> leftNode<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 删除二分搜索树中最小值的元素的节点，并返回这个节点 递归算法 -</span>
    <span class="token function">recursiveRemoveMin</span><span class="token punctuation">(</span><span class="token parameter">node</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 解决最简单的问题</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>left <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> rightNode <span class="token operator">=</span> node<span class="token punctuation">.</span>right<span class="token punctuation">;</span>
        node<span class="token punctuation">.</span>right <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token operator">--</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> rightNode<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 将复杂的问题拆分为性质相同的小问题，</span>
        <span class="token comment">// 然后求出这些小问题的解后构建出原问题的答案</span>
        node<span class="token punctuation">.</span>left <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveRemoveMin</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>left<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> node<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 删除二分搜索树上的任意节点</span>
    <span class="token function">remove</span><span class="token punctuation">(</span><span class="token parameter">element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>root <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveRemove</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">,</span> element<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 删除二分搜索树上的任意节点 递归算法</span>
    <span class="token comment">// 返回删除对应元素节点后新的二分搜索树的根</span>
    <span class="token function">recursiveRemove</span><span class="token punctuation">(</span><span class="token parameter">node<span class="token punctuation">,</span> element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token keyword">null</span><span class="token punctuation">;</span>

        <span class="token comment">// 当前节点的元素值比待删除的元素小  那么就向当前节点的右子树中去找</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">compare</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">,</span> element<span class="token punctuation">)</span> <span class="token operator">&lt;</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        node<span class="token punctuation">.</span>right <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveRemove</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">,</span> element<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> node<span class="token punctuation">;</span>
        <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">compare</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">,</span> element<span class="token punctuation">)</span> <span class="token operator">&gt;</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 向当前节点的左子树中去找</span>
        node<span class="token punctuation">.</span>left <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveRemove</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>left<span class="token punctuation">,</span> element<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> node<span class="token punctuation">;</span>
        <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span>
        <span class="token comment">// 如果找到了相同值的节点了，开始进行相应的处理</span>

        <span class="token comment">// 如果这个节点左子树为空，那么就让这个节点的右子树覆盖当前节点</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>left <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">let</span> rightNode <span class="token operator">=</span> node<span class="token punctuation">.</span>right<span class="token punctuation">;</span>
            node<span class="token punctuation">.</span>right <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
            <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token operator">--</span><span class="token punctuation">;</span>
            <span class="token keyword">return</span> rightNode<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 如果当前节点的右子树为空，那么就让这个节点的左子树覆盖当前节点</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>right <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">let</span> leftNode <span class="token operator">=</span> node<span class="token punctuation">.</span>left<span class="token punctuation">;</span>
            node<span class="token punctuation">.</span>left <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
            <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token operator">--</span><span class="token punctuation">;</span>
            <span class="token keyword">return</span> leftNode<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 如果当前节点的左右子树都不为空，那么就开始特殊操作</span>
        <span class="token comment">// 1. 先找到当前节点右子树上最小的那个节点，保存起来</span>
        <span class="token comment">// 2. 然后删除掉当前节点右子树上最小的那个节点，</span>
        <span class="token comment">// 3. 让保存起来的那个节点覆盖掉当前节点</span>
        <span class="token comment">//    1. 也就是保存起来的那个节点的right = 删除掉当前节点右子树上最小的节点后返回的那个节点</span>
        <span class="token comment">//    2. 再让保存起来的那个节点的left = 当前节点的left</span>
        <span class="token comment">// 4. 解除当前节点及其left和right，全都赋值为null，这样就相当于把当前节点从二分搜索树中剔除了</span>
        <span class="token comment">// 5. 返回保存的这个节点</span>

        <span class="token keyword">let</span> successtor <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveMinimum</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">)</span><span class="token punctuation">;</span>
        successtor<span class="token punctuation">.</span>right <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveRemoveMin</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token comment">// 恢复removeMin 操作的this.size -- 带来的影响</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token operator">++</span><span class="token punctuation">;</span>

        successtor<span class="token punctuation">.</span>left <span class="token operator">=</span> node<span class="token punctuation">.</span>left<span class="token punctuation">;</span>

        <span class="token comment">// 开始正式的删除当前节点的操作</span>
        node <span class="token operator">=</span> node<span class="token punctuation">.</span>left <span class="token operator">=</span> node<span class="token punctuation">.</span>right <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token operator">--</span><span class="token punctuation">;</span>

        <span class="token comment">// 返回当前保存的节点</span>
        <span class="token keyword">return</span> successtor<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 前序遍历 +</span>
    <span class="token function">preOrder</span><span class="token punctuation">(</span><span class="token parameter">operator</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursivePreOrder</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">,</span> operator<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 前序遍历 递归算法 -</span>
    <span class="token function">recursivePreOrder</span><span class="token punctuation">(</span><span class="token parameter">node<span class="token punctuation">,</span> operator</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span><span class="token punctuation">;</span>

        <span class="token comment">// 调用一下操作方法</span>
        <span class="token function">operator</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>
        console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>node<span class="token punctuation">,</span> node<span class="token punctuation">.</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token comment">// 继续递归遍历左右子树</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursivePreOrder</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>left<span class="token punctuation">,</span> operator<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursivePreOrder</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">,</span> operator<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 前序遍历 非递归算法 +</span>
    <span class="token function">nonRecursivePreOrder</span><span class="token punctuation">(</span><span class="token parameter">operator</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> stack <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">MyLinkedListStack</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        stack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token operator">!</span>stack<span class="token punctuation">.</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 出栈操作</span>
        node <span class="token operator">=</span> stack<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token function">operator</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 访问当前的节点</span>
        console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token comment">// 栈是先入后出的，把需要后访问的节点 先放进去，先访问的节点后放进去</span>
        <span class="token comment">// 前序遍历是访问当前节点，然后再遍历左子树，最后遍历右子树</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>right <span class="token operator">!==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> stack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>left <span class="token operator">!==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> stack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>left<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 中序遍历 +</span>
    <span class="token function">inOrder</span><span class="token punctuation">(</span><span class="token parameter">operator</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveInOrder</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">,</span> operator<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 中序遍历 递归算法 -</span>
    <span class="token function">recursiveInOrder</span><span class="token punctuation">(</span><span class="token parameter">node<span class="token punctuation">,</span> operator</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span><span class="token punctuation">;</span>

        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveInOrder</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>left<span class="token punctuation">,</span> operator<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token function">operator</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>
        console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursiveInOrder</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">,</span> operator<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 后序遍历 +</span>
    <span class="token function">postOrder</span><span class="token punctuation">(</span><span class="token parameter">operator</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursivePostOrder</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">,</span> operator<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 后序遍历 递归算法 -</span>
    <span class="token function">recursivePostOrder</span><span class="token punctuation">(</span><span class="token parameter">node<span class="token punctuation">,</span> operator</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node <span class="token operator">==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token keyword">return</span><span class="token punctuation">;</span>

        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursivePostOrder</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>left<span class="token punctuation">,</span> operator<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">recursivePostOrder</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">,</span> operator<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token function">operator</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>
        console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 层序遍历</span>
    <span class="token function">levelOrder</span><span class="token punctuation">(</span><span class="token parameter">operator</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> queue <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">MyLinkedListQueue</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        queue<span class="token punctuation">.</span><span class="token function">enqueue</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">let</span> node <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>
        <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token operator">!</span>queue<span class="token punctuation">.</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        node <span class="token operator">=</span> queue<span class="token punctuation">.</span><span class="token function">dequeue</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token function">operator</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>
        console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token comment">// 队列 是先进先出的，所以从左往右入队</span>
        <span class="token comment">// 栈  是后进先出的， 所以从右往左入栈</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>left <span class="token operator">!==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> queue<span class="token punctuation">.</span><span class="token function">enqueue</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>left<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">if</span> <span class="token punctuation">(</span>node<span class="token punctuation">.</span>right <span class="token operator">!==</span> <span class="token keyword">null</span><span class="token punctuation">)</span> queue<span class="token punctuation">.</span><span class="token function">enqueue</span><span class="token punctuation">(</span>node<span class="token punctuation">.</span>right<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 获取二分搜索树中节点个数 +</span>
    <span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>size<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 返回二分搜索树是否为空的bool值 +</span>
    <span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>size <span class="token operator">===</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 新增一个比较的方法，专门用来比较新增的元素大小 -</span>
    <span class="token comment">// 第一个元素比第二个元素大 就返回 1</span>
    <span class="token comment">// 第一个元素比第二个元素小 就返回 -1</span>
    <span class="token comment">// 第一个元素比第二个元素相等 就返回 0</span>
    <span class="token function">compare</span><span class="token punctuation">(</span><span class="token parameter">elementA<span class="token punctuation">,</span> elementB</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>elementA <span class="token operator">===</span> <span class="token keyword">null</span> <span class="token operator">||</span> elementB <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span>
        <span class="token keyword">throw</span> <span class="token keyword">new</span> <span class="token class-name">Error</span><span class="token punctuation">(</span><span class="token string">&quot;element is null. can't compare.&quot;</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token comment">// 先直接写死</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>elementA <span class="token operator">&gt;</span> elementB<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>elementA <span class="token operator">&lt;</span> elementB<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token keyword">else</span> <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 输出二分搜索树中的信息</span>
    <span class="token comment">// @Override toString 2018-11-03-jwl</span>
    <span class="token function">toString</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> treeInfo <span class="token operator">=</span> <span class="token string">''</span><span class="token punctuation">;</span>
        treeInfo <span class="token operator">+=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">getBinarySearchTreeString</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>root<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> treeInfo<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> treeInfo<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 写一个辅助函数，用来生成二分搜索树信息的字符串</span>
    <span class="token function">getBinarySearchTreeString</span><span class="token punctuation">(</span>node<span class="token punctuation">,</span> depth<span class="token punctuation">,</span> treeInfo<span class="token punctuation">,</span> pageContent <span class="token operator">=</span> <span class="token string">''</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">//以前序遍历的方式</span>

        <span class="token keyword">if</span> <span class="token punctuation">(</span>node <span class="token operator">===</span> <span class="token keyword">null</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        treeInfo <span class="token operator">+=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">getDepthString</span><span class="token punctuation">(</span>depth<span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token string">'null \r\n'</span><span class="token punctuation">;</span>

        pageContent <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">getDepthString</span><span class="token punctuation">(</span>depth<span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token string">'null&lt;br /&gt;&lt;br /&gt;'</span><span class="token punctuation">;</span>
        document<span class="token punctuation">.</span>body<span class="token punctuation">.</span>innerHTML <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>pageContent<span class="token interpolation-punctuation punctuation">}</span></span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>

        <span class="token keyword">return</span> treeInfo<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        treeInfo <span class="token operator">+=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">getDepthString</span><span class="token punctuation">(</span>depth<span class="token punctuation">)</span> <span class="token operator">+</span> node<span class="token punctuation">.</span>element <span class="token operator">+</span> <span class="token string">'\r\n'</span><span class="token punctuation">;</span>

        pageContent <span class="token operator">=</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">getDepthString</span><span class="token punctuation">(</span>depth<span class="token punctuation">)</span> <span class="token operator">+</span> node<span class="token punctuation">.</span>element <span class="token operator">+</span> <span class="token string">'&lt;br /&gt;&lt;br /&gt;'</span><span class="token punctuation">;</span>
        document<span class="token punctuation">.</span>body<span class="token punctuation">.</span>innerHTML <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>pageContent<span class="token interpolation-punctuation punctuation">}</span></span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>

        treeInfo <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">getBinarySearchTreeString</span><span class="token punctuation">(</span>
        node<span class="token punctuation">.</span>left<span class="token punctuation">,</span>
        depth <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span>
        treeInfo
        <span class="token punctuation">)</span><span class="token punctuation">;</span>
        treeInfo <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">getBinarySearchTreeString</span><span class="token punctuation">(</span>
        node<span class="token punctuation">.</span>right<span class="token punctuation">,</span>
        depth <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span>
        treeInfo
        <span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">return</span> treeInfo<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 写一个辅助函数，用来生成递归深度字符串</span>
    <span class="token function">getDepthString</span><span class="token punctuation">(</span><span class="token parameter">depth</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> depthString <span class="token operator">=</span> <span class="token string">''</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> depth<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        depthString <span class="token operator">+=</span> <span class="token string">'-- '</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">return</span> depthString<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><p><strong>PerformanceTest</strong></p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token comment">// 性能测试</span>
<span class="token keyword">class</span> <span class="token class-name">PerformanceTest</span> <span class="token punctuation">{</span>
    <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span><span class="token punctuation">}</span>

    <span class="token comment">// 对比都列</span>
    <span class="token function">testQueue</span><span class="token punctuation">(</span><span class="token parameter">queue<span class="token punctuation">,</span> openCount</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> startTime <span class="token operator">=</span> Date<span class="token punctuation">.</span><span class="token function">now</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">let</span> random <span class="token operator">=</span> Math<span class="token punctuation">.</span>random<span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> openCount<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        queue<span class="token punctuation">.</span><span class="token function">enqueue</span><span class="token punctuation">(</span><span class="token function">random</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">*</span> openCount<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token operator">!</span>queue<span class="token punctuation">.</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        queue<span class="token punctuation">.</span><span class="token function">dequeue</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">let</span> endTime <span class="token operator">=</span> Date<span class="token punctuation">.</span><span class="token function">now</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">calcTime</span><span class="token punctuation">(</span>endTime <span class="token operator">-</span> startTime<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 对比栈</span>
    <span class="token function">testStack</span><span class="token punctuation">(</span><span class="token parameter">stack<span class="token punctuation">,</span> openCount</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> startTime <span class="token operator">=</span> Date<span class="token punctuation">.</span><span class="token function">now</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">let</span> random <span class="token operator">=</span> Math<span class="token punctuation">.</span>random<span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> openCount<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        stack<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token function">random</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">*</span> openCount<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token operator">!</span>stack<span class="token punctuation">.</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        stack<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">let</span> endTime <span class="token operator">=</span> Date<span class="token punctuation">.</span><span class="token function">now</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">calcTime</span><span class="token punctuation">(</span>endTime <span class="token operator">-</span> startTime<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 对比集合</span>
    <span class="token function">testSet</span><span class="token punctuation">(</span><span class="token parameter">set<span class="token punctuation">,</span> openCount</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> startTime <span class="token operator">=</span> Date<span class="token punctuation">.</span><span class="token function">now</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">let</span> random <span class="token operator">=</span> Math<span class="token punctuation">.</span>random<span class="token punctuation">;</span>
        <span class="token keyword">let</span> arr <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token keyword">let</span> temp <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>

        <span class="token comment">// 第一遍测试</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> openCount<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        temp <span class="token operator">=</span> <span class="token function">random</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment">// 添加重复元素，从而测试集合去重的能力</span>
        set<span class="token punctuation">.</span><span class="token function">add</span><span class="token punctuation">(</span>temp <span class="token operator">*</span> openCount<span class="token punctuation">)</span><span class="token punctuation">;</span>
        set<span class="token punctuation">.</span><span class="token function">add</span><span class="token punctuation">(</span>temp <span class="token operator">*</span> openCount<span class="token punctuation">)</span><span class="token punctuation">;</span>

        arr<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>temp <span class="token operator">*</span> openCount<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> openCount<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        set<span class="token punctuation">.</span><span class="token function">remove</span><span class="token punctuation">(</span>arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">// 第二遍测试</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> openCount<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        set<span class="token punctuation">.</span><span class="token function">add</span><span class="token punctuation">(</span>arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        set<span class="token punctuation">.</span><span class="token function">add</span><span class="token punctuation">(</span>arr<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token operator">!</span>set<span class="token punctuation">.</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        set<span class="token punctuation">.</span><span class="token function">remove</span><span class="token punctuation">(</span>arr<span class="token punctuation">[</span>set<span class="token punctuation">.</span><span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">let</span> endTime <span class="token operator">=</span> Date<span class="token punctuation">.</span><span class="token function">now</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token comment">// 求出两次测试的平均时间</span>
        <span class="token keyword">let</span> avgTime <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">ceil</span><span class="token punctuation">(</span><span class="token punctuation">(</span>endTime <span class="token operator">-</span> startTime<span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">calcTime</span><span class="token punctuation">(</span>avgTime<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 计算运行的时间，转换为 天-小时-分钟-秒-毫秒</span>
    <span class="token function">calcTime</span><span class="token punctuation">(</span><span class="token parameter">result</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">//获取距离的天数</span>
        <span class="token keyword">var</span> day <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">floor</span><span class="token punctuation">(</span>result <span class="token operator">/</span> <span class="token punctuation">(</span><span class="token number">24</span> <span class="token operator">*</span> <span class="token number">60</span> <span class="token operator">*</span> <span class="token number">60</span> <span class="token operator">*</span> <span class="token number">1000</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token comment">//获取距离的小时数</span>
        <span class="token keyword">var</span> hours <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">floor</span><span class="token punctuation">(</span><span class="token punctuation">(</span>result <span class="token operator">/</span> <span class="token punctuation">(</span><span class="token number">60</span> <span class="token operator">*</span> <span class="token number">60</span> <span class="token operator">*</span> <span class="token number">1000</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">%</span> <span class="token number">24</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token comment">//获取距离的分钟数</span>
        <span class="token keyword">var</span> minutes <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">floor</span><span class="token punctuation">(</span><span class="token punctuation">(</span>result <span class="token operator">/</span> <span class="token punctuation">(</span><span class="token number">60</span> <span class="token operator">*</span> <span class="token number">1000</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">%</span> <span class="token number">60</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token comment">//获取距离的秒数</span>
        <span class="token keyword">var</span> seconds <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">floor</span><span class="token punctuation">(</span><span class="token punctuation">(</span>result <span class="token operator">/</span> <span class="token number">1000</span><span class="token punctuation">)</span> <span class="token operator">%</span> <span class="token number">60</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token comment">//获取距离的毫秒数</span>
        <span class="token keyword">var</span> milliSeconds <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">floor</span><span class="token punctuation">(</span>result <span class="token operator">%</span> <span class="token number">1000</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token comment">// 计算时间</span>
        day <span class="token operator">=</span> day <span class="token operator">&lt;</span> <span class="token number">10</span> <span class="token operator">?</span> <span class="token string">'0'</span> <span class="token operator">+</span> day <span class="token operator">:</span> day<span class="token punctuation">;</span>
        hours <span class="token operator">=</span> hours <span class="token operator">&lt;</span> <span class="token number">10</span> <span class="token operator">?</span> <span class="token string">'0'</span> <span class="token operator">+</span> hours <span class="token operator">:</span> hours<span class="token punctuation">;</span>
        minutes <span class="token operator">=</span> minutes <span class="token operator">&lt;</span> <span class="token number">10</span> <span class="token operator">?</span> <span class="token string">'0'</span> <span class="token operator">+</span> minutes <span class="token operator">:</span> minutes<span class="token punctuation">;</span>
        seconds <span class="token operator">=</span> seconds <span class="token operator">&lt;</span> <span class="token number">10</span> <span class="token operator">?</span> <span class="token string">'0'</span> <span class="token operator">+</span> seconds <span class="token operator">:</span> seconds<span class="token punctuation">;</span>
        milliSeconds <span class="token operator">=</span>
        milliSeconds <span class="token operator">&lt;</span> <span class="token number">100</span>
            <span class="token operator">?</span> milliSeconds <span class="token operator">&lt;</span> <span class="token number">10</span>
                <span class="token operator">?</span> <span class="token string">'00'</span> <span class="token operator">+</span> milliSeconds
                <span class="token operator">:</span> <span class="token string">'0'</span> <span class="token operator">+</span> milliSeconds
            <span class="token operator">:</span> milliSeconds<span class="token punctuation">;</span>

        <span class="token comment">// 输出耗时字符串</span>
        result <span class="token operator">=</span>
        day <span class="token operator">+</span>
        <span class="token string">'天'</span> <span class="token operator">+</span>
        hours <span class="token operator">+</span>
        <span class="token string">'小时'</span> <span class="token operator">+</span>
        minutes <span class="token operator">+</span>
        <span class="token string">'分'</span> <span class="token operator">+</span>
        seconds <span class="token operator">+</span>
        <span class="token string">'秒'</span> <span class="token operator">+</span>
        milliSeconds <span class="token operator">+</span>
        <span class="token string">'毫秒'</span> <span class="token operator">+</span>
        <span class="token string">'  &lt;&lt;&lt;&lt;============&gt;&gt;&gt;&gt;  总毫秒数：'</span> <span class="token operator">+</span>
        result<span class="token punctuation">;</span>

        <span class="token keyword">return</span> result<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><p><strong>MyLinkedListSet</strong></p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token comment">// 自定义链表集合Set</span>
<span class="token keyword">class</span> <span class="token class-name">MyLinkedListSet</span> <span class="token punctuation">{</span>
    <span class="token comment">//</span>
    <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>myLinkedList <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">MyLinkedList</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token function">add</span><span class="token punctuation">(</span><span class="token parameter">element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span><span class="token keyword">this</span><span class="token punctuation">.</span>myLinkedList<span class="token punctuation">.</span><span class="token function">contains</span><span class="token punctuation">(</span>element<span class="token punctuation">)</span><span class="token punctuation">)</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>myLinkedList<span class="token punctuation">.</span><span class="token function">addFirst</span><span class="token punctuation">(</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token function">remove</span><span class="token punctuation">(</span><span class="token parameter">element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>myLinkedList<span class="token punctuation">.</span><span class="token function">removeElement</span><span class="token punctuation">(</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token function">contains</span><span class="token punctuation">(</span><span class="token parameter">element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>myLinkedList<span class="token punctuation">.</span><span class="token function">contains</span><span class="token punctuation">(</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token function">each</span><span class="token punctuation">(</span><span class="token parameter">operator</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> size <span class="token operator">=</span> <span class="token keyword">this</span><span class="token punctuation">.</span>myLinkedList<span class="token punctuation">.</span><span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">var</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> size<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token function">operator</span><span class="token punctuation">(</span><span class="token keyword">this</span><span class="token punctuation">.</span>myLinkedList<span class="token punctuation">.</span><span class="token function">get</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>myLinkedList<span class="token punctuation">.</span><span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>myLinkedList<span class="token punctuation">.</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><p><strong>MyBSTSet</strong></p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token comment">// 自定义二分搜索树集合Set</span>
<span class="token keyword">class</span> <span class="token class-name">MyBinarySearchTreeSet</span> <span class="token punctuation">{</span>
    <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 借用二分搜索树来实现这个接口</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>myBinarySearchTree <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">MyBinarySearchTree</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 添加元素</span>
    <span class="token function">add</span><span class="token punctuation">(</span><span class="token parameter">element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>myBinarySearchTree<span class="token punctuation">.</span><span class="token function">add</span><span class="token punctuation">(</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 移除元素</span>
    <span class="token function">remove</span><span class="token punctuation">(</span><span class="token parameter">element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span>myBinarySearchTree<span class="token punctuation">.</span><span class="token function">remove</span><span class="token punctuation">(</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 是否包含这个元素</span>
    <span class="token function">contains</span><span class="token punctuation">(</span><span class="token parameter">element</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>myBinarySearchTree<span class="token punctuation">.</span><span class="token function">contains</span><span class="token punctuation">(</span>element<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 遍历操作</span>
    <span class="token comment">// 第一个参数 是回掉函数，</span>
    <span class="token comment">// 第二个参数 是遍历的方式 深度优先遍历(前pre、中in、后post)，广度优先遍历(层序level)</span>
    <span class="token function">each</span><span class="token punctuation">(</span><span class="token parameter">operator<span class="token punctuation">,</span> method</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 遍历方式默认是非递归的前序遍历，</span>
        <span class="token comment">// 其它的遍历方式就是递归的前、中、后、层序遍历。</span>
        <span class="token keyword">switch</span> <span class="token punctuation">(</span>method<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">case</span> <span class="token string">'pre'</span><span class="token operator">:</span>
            <span class="token keyword">this</span><span class="token punctuation">.</span>myBinarySearchTree<span class="token punctuation">.</span><span class="token function">preOrder</span><span class="token punctuation">(</span>operator<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">break</span><span class="token punctuation">;</span>
        <span class="token keyword">case</span> <span class="token string">'in'</span><span class="token operator">:</span>
            <span class="token keyword">this</span><span class="token punctuation">.</span>myBinarySearchTree<span class="token punctuation">.</span><span class="token function">inOrder</span><span class="token punctuation">(</span>operator<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">break</span><span class="token punctuation">;</span>
        <span class="token keyword">case</span> <span class="token string">'post'</span><span class="token operator">:</span>
            <span class="token keyword">this</span><span class="token punctuation">.</span>myBinarySearchTree<span class="token punctuation">.</span><span class="token function">postOrder</span><span class="token punctuation">(</span>operator<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">break</span><span class="token punctuation">;</span>
        <span class="token keyword">case</span> <span class="token string">'level'</span><span class="token operator">:</span>
            <span class="token keyword">this</span><span class="token punctuation">.</span>myBinarySearchTree<span class="token punctuation">.</span><span class="token function">levelOrder</span><span class="token punctuation">(</span>operator<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">break</span><span class="token punctuation">;</span>
        <span class="token keyword">default</span><span class="token operator">:</span>
            <span class="token keyword">this</span><span class="token punctuation">.</span>myBinarySearchTree<span class="token punctuation">.</span><span class="token function">nonRecursivePreOrder</span><span class="token punctuation">(</span>operator<span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token keyword">break</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 获取集合中实际的元素个数</span>
    <span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>myBinarySearchTree<span class="token punctuation">.</span><span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 返回集合是否为空的bool值</span>
    <span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">return</span> <span class="token keyword">this</span><span class="token punctuation">.</span>myBinarySearchTree<span class="token punctuation">.</span><span class="token function">isEmpty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><p><strong>Main</strong></p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token comment">// main 函数</span>
<span class="token keyword">class</span> <span class="token class-name">Main</span> <span class="token punctuation">{</span>
    <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">alterLine</span><span class="token punctuation">(</span><span class="token string">'Set Comparison Area'</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">let</span> myLinkedListSet <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">MyLinkedListSet</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">let</span> myBinarySearchTreeSet <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">MyBinarySearchTreeSet</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">let</span> performanceTest <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">PerformanceTest</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">let</span> myLinkedListSetInfo <span class="token operator">=</span> performanceTest<span class="token punctuation">.</span><span class="token function">testSet</span><span class="token punctuation">(</span>
        myLinkedListSet<span class="token punctuation">,</span>
        <span class="token number">5000</span>
        <span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">let</span> myBinarySearchTreeSetInfo <span class="token operator">=</span> performanceTest<span class="token punctuation">.</span><span class="token function">testSet</span><span class="token punctuation">(</span>
        myBinarySearchTreeSet<span class="token punctuation">,</span>
        <span class="token number">5000</span>
        <span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">alterLine</span><span class="token punctuation">(</span><span class="token string">'MyLinkedListSet Area'</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>myLinkedListSetInfo<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">show</span><span class="token punctuation">(</span>myLinkedListSetInfo<span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">alterLine</span><span class="token punctuation">(</span><span class="token string">'MyBinarySearchTreeSet Area'</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>myBinarySearchTreeSetInfo<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">show</span><span class="token punctuation">(</span>myBinarySearchTreeSetInfo<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 将内容显示在页面上</span>
    <span class="token function">show</span><span class="token punctuation">(</span><span class="token parameter">content</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        document<span class="token punctuation">.</span>body<span class="token punctuation">.</span>innerHTML <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>content<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">&lt;br /&gt;&lt;br /&gt;</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 展示分割线</span>
    <span class="token function">alterLine</span><span class="token punctuation">(</span><span class="token parameter">title</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> line <span class="token operator">=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token string">--------------------</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>title<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">----------------------</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
        console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>line<span class="token punctuation">)</span><span class="token punctuation">;</span>
        document<span class="token punctuation">.</span>body<span class="token punctuation">.</span>innerHTML <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>line<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">&lt;br /&gt;&lt;br /&gt;</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

<span class="token comment">// 页面加载完毕</span>
window<span class="token punctuation">.</span><span class="token function-variable function">onload</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token comment">// 执行主函数</span>
    <span class="token keyword">new</span> <span class="token class-name">Main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre></div><h2 id="总结"><a href="#总结" class="header-anchor">#</a> 总结</h2> <p>在计算机的世界中，集合是一种非常有用的一种数据结构，集合在生活中可以做客户统计、词汇量统计。在很多算法面试题来说，集合也是有很大的作用的。</p> <p>虽然我们实现了自己专属集合，仅供学习数据结构中的算法思想。生产端还是要使用 内置的集合，内置的 Set 比自己实现的 MyBSTSet 要强大很多。因为 底层实现 Set 的树结构是一个平衡二叉树，更准确的说是基于红黑树来进行实现的，所以这个 Set 不会出现最差的时间复杂度<code>O(n)</code>的情况，在最差的情况下在 Set 中进行增删查也是<code>O(logn)</code>这种级别。并且这个 Set 还定义了更多的操作，这些操作都是和二分搜索树具有顺序性相关的操作。</p> <h2 id="拓展"><a href="#拓展" class="header-anchor">#</a> 拓展</h2> <h3 id="leetcode-804-唯一摩尔斯密码词"><a href="#leetcode-804-唯一摩尔斯密码词" class="header-anchor">#</a> leetcode 804.唯一摩尔斯密码词</h3> <p>网址：<code>https://leetcode-cn.com/problems/unique-morse-code-words/</code><br>
解答</p> <div class="language-js extra-class"><pre class="language-js"><code><span class="token comment">// 答题</span>
<span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
    <span class="token comment">// leetcode 804. 唯一摩尔斯密码词</span>
    <span class="token function">uniqueMorseRepresentations</span><span class="token punctuation">(</span><span class="token parameter">words</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">/**
         * @param {string[]} words
         * @return {number}
         * 使用自己的二分搜索树来实现
         */</span>
        <span class="token keyword">var</span> <span class="token function-variable function">uniqueMorseRepresentations</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">words</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 摩斯码</span>
        <span class="token keyword">const</span> codes <span class="token operator">=</span> <span class="token punctuation">[</span>
            <span class="token string">'.-'</span><span class="token punctuation">,</span>
            <span class="token string">'-...'</span><span class="token punctuation">,</span>
            <span class="token string">'-.-.'</span><span class="token punctuation">,</span>
            <span class="token string">'-..'</span><span class="token punctuation">,</span>
            <span class="token string">'.'</span><span class="token punctuation">,</span>
            <span class="token string">'..-.'</span><span class="token punctuation">,</span>
            <span class="token string">'--.'</span><span class="token punctuation">,</span>
            <span class="token string">'....'</span><span class="token punctuation">,</span>
            <span class="token string">'..'</span><span class="token punctuation">,</span>
            <span class="token string">'.---'</span><span class="token punctuation">,</span>
            <span class="token string">'-.-'</span><span class="token punctuation">,</span>
            <span class="token string">'.-..'</span><span class="token punctuation">,</span>
            <span class="token string">'--'</span><span class="token punctuation">,</span>
            <span class="token string">'-.'</span><span class="token punctuation">,</span>
            <span class="token string">'---'</span><span class="token punctuation">,</span>
            <span class="token string">'.--.'</span><span class="token punctuation">,</span>
            <span class="token string">'--.-'</span><span class="token punctuation">,</span>
            <span class="token string">'.-.'</span><span class="token punctuation">,</span>
            <span class="token string">'...'</span><span class="token punctuation">,</span>
            <span class="token string">'-'</span><span class="token punctuation">,</span>
            <span class="token string">'..-'</span><span class="token punctuation">,</span>
            <span class="token string">'...-'</span><span class="token punctuation">,</span>
            <span class="token string">'.--'</span><span class="token punctuation">,</span>
            <span class="token string">'-..-'</span><span class="token punctuation">,</span>
            <span class="token string">'-.--'</span><span class="token punctuation">,</span>
            <span class="token string">'--..'</span>
        <span class="token punctuation">]</span><span class="token punctuation">;</span>

        <span class="token keyword">const</span> myBinarySearchTreeSet <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">MyBinarySearchTreeSet</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">let</span> content <span class="token operator">=</span> <span class="token string">''</span><span class="token punctuation">;</span>
        <span class="token comment">// 获取起始字符的aceii码，</span>
        <span class="token comment">// 从而可以求出某个单词的每一个字符在字母表中占的位置索引，</span>
        <span class="token comment">// 根据这些位置索引就可以在摩斯表中找到相应的摩斯码，</span>
        <span class="token comment">// 一个单词就是一组摩斯码，然后使用set添加，就可以直接实现去重的操作了</span>
        <span class="token keyword">const</span> start <span class="token operator">=</span> <span class="token string">'a'</span><span class="token punctuation">.</span><span class="token function">charCodeAt</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">const</span> word <span class="token keyword">of</span> words<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">const</span> w <span class="token keyword">of</span> word<span class="token punctuation">)</span> content <span class="token operator">+=</span> codes<span class="token punctuation">[</span>w<span class="token punctuation">.</span><span class="token function">charCodeAt</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span> <span class="token operator">-</span> start<span class="token punctuation">]</span><span class="token punctuation">;</span>

            myBinarySearchTreeSet<span class="token punctuation">.</span><span class="token function">add</span><span class="token punctuation">(</span>content<span class="token punctuation">)</span><span class="token punctuation">;</span>
            content <span class="token operator">=</span> <span class="token string">''</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">return</span> myBinarySearchTreeSet<span class="token punctuation">.</span><span class="token function">getSize</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span><span class="token punctuation">;</span>

        <span class="token comment">/**
         * @param {string[]} words
         * @return {number}
         * 使用系统内置的Set集合类
         */</span>
        <span class="token keyword">var</span> <span class="token function-variable function">uniqueMorseRepresentations</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">words</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// 摩斯码</span>
        <span class="token keyword">const</span> codes <span class="token operator">=</span> <span class="token punctuation">[</span>
            <span class="token string">'.-'</span><span class="token punctuation">,</span>
            <span class="token string">'-...'</span><span class="token punctuation">,</span>
            <span class="token string">'-.-.'</span><span class="token punctuation">,</span>
            <span class="token string">'-..'</span><span class="token punctuation">,</span>
            <span class="token string">'.'</span><span class="token punctuation">,</span>
            <span class="token string">'..-.'</span><span class="token punctuation">,</span>
            <span class="token string">'--.'</span><span class="token punctuation">,</span>
            <span class="token string">'....'</span><span class="token punctuation">,</span>
            <span class="token string">'..'</span><span class="token punctuation">,</span>
            <span class="token string">'.---'</span><span class="token punctuation">,</span>
            <span class="token string">'-.-'</span><span class="token punctuation">,</span>
            <span class="token string">'.-..'</span><span class="token punctuation">,</span>
            <span class="token string">'--'</span><span class="token punctuation">,</span>
            <span class="token string">'-.'</span><span class="token punctuation">,</span>
            <span class="token string">'---'</span><span class="token punctuation">,</span>
            <span class="token string">'.--.'</span><span class="token punctuation">,</span>
            <span class="token string">'--.-'</span><span class="token punctuation">,</span>
            <span class="token string">'.-.'</span><span class="token punctuation">,</span>
            <span class="token string">'...'</span><span class="token punctuation">,</span>
            <span class="token string">'-'</span><span class="token punctuation">,</span>
            <span class="token string">'..-'</span><span class="token punctuation">,</span>
            <span class="token string">'...-'</span><span class="token punctuation">,</span>
            <span class="token string">'.--'</span><span class="token punctuation">,</span>
            <span class="token string">'-..-'</span><span class="token punctuation">,</span>
            <span class="token string">'-.--'</span><span class="token punctuation">,</span>
            <span class="token string">'--..'</span>
        <span class="token punctuation">]</span><span class="token punctuation">;</span>

        <span class="token keyword">const</span> set <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Set</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">let</span> content <span class="token operator">=</span> <span class="token string">''</span><span class="token punctuation">;</span>
        <span class="token comment">// 获取起始字符的aceii码，</span>
        <span class="token comment">// 从而可以求出某个单词的每一个字符在字母表中占的位置索引，</span>
        <span class="token comment">// 根据这些位置索引就可以在摩斯表中找到相应的摩斯码，</span>
        <span class="token comment">// 一个单词就是一组摩斯码，然后使用set添加，就可以直接实现去重的操作了</span>
        <span class="token keyword">const</span> start <span class="token operator">=</span> <span class="token string">'a'</span><span class="token punctuation">.</span><span class="token function">charCodeAt</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">const</span> word <span class="token keyword">of</span> words<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">const</span> w <span class="token keyword">of</span> word<span class="token punctuation">)</span> content <span class="token operator">+=</span> codes<span class="token punctuation">[</span>w<span class="token punctuation">.</span><span class="token function">charCodeAt</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span> <span class="token operator">-</span> start<span class="token punctuation">]</span><span class="token punctuation">;</span>

            set<span class="token punctuation">.</span><span class="token function">add</span><span class="token punctuation">(</span>content<span class="token punctuation">)</span><span class="token punctuation">;</span>
            content <span class="token operator">=</span> <span class="token string">''</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">return</span> set<span class="token punctuation">.</span>size<span class="token punctuation">;</span>
        <span class="token punctuation">}</span><span class="token punctuation">;</span>

        <span class="token keyword">return</span> <span class="token function">uniqueMorseRepresentations</span><span class="token punctuation">(</span>words<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token comment">// main 函数</span>
<span class="token keyword">class</span> <span class="token class-name">Main</span> <span class="token punctuation">{</span>
    <span class="token function">constructor</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">alterLine</span><span class="token punctuation">(</span><span class="token string">'leetcode 804.唯一摩尔斯密码词'</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">let</span> s <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">Solution</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">let</span> words <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token string">'gin'</span><span class="token punctuation">,</span> <span class="token string">'zen'</span><span class="token punctuation">,</span> <span class="token string">'gig'</span><span class="token punctuation">,</span> <span class="token string">'msg'</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token keyword">this</span><span class="token punctuation">.</span><span class="token function">show</span><span class="token punctuation">(</span>s<span class="token punctuation">.</span><span class="token function">uniqueMorseRepresentations</span><span class="token punctuation">(</span>words<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 将内容显示在页面上</span>
    <span class="token function">show</span><span class="token punctuation">(</span><span class="token parameter">content</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        document<span class="token punctuation">.</span>body<span class="token punctuation">.</span>innerHTML <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>content<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">&lt;br /&gt;&lt;br /&gt;</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token comment">// 展示分割线</span>
    <span class="token function">alterLine</span><span class="token punctuation">(</span><span class="token parameter">title</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">let</span> line <span class="token operator">=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token string">--------------------</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>title<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">----------------------</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
        console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>line<span class="token punctuation">)</span><span class="token punctuation">;</span>
        document<span class="token punctuation">.</span>body<span class="token punctuation">.</span>innerHTML <span class="token operator">+=</span> <span class="token template-string"><span class="token template-punctuation string">`</span><span class="token interpolation"><span class="token interpolation-punctuation punctuation">${</span>line<span class="token interpolation-punctuation punctuation">}</span></span><span class="token string">&lt;br /&gt;&lt;br /&gt;</span><span class="token template-punctuation string">`</span></span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

<span class="token comment">// 页面加载完毕</span>
window<span class="token punctuation">.</span><span class="token function-variable function">onload</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token comment">// 执行主函数</span>
    <span class="token keyword">new</span> <span class="token class-name">Main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre></div><h3 id="有序集合和无序集合"><a href="#有序集合和无序集合" class="header-anchor">#</a> 有序集合和无序集合</h3> <p>之前实现的集合是基于二分搜索树实现的集合，还有 系统内置的基于红黑树实现的集合，它们本质都是有序的集合。</p> <p>有序的集合是指元素在集合中是具有顺序性的。例如在二分搜索树中存储的元素，可以很轻易地从小到大遍历出来或者去看这个元素的是上或下一个元素是谁等等，这个准确的来说就是有序集合(OrderSet)。</p> <p>无序的集合是指元素在集合中是没有顺序的。例如在链表中存储的元素，只是根据元素插入的顺序来决定这些元素在集合中的顺序，不能够轻易地从小到大来遍历在这个集合中所有的元素，也无法非常容易的去找到这个集合中最小最大的元素是谁、上或下一个元素谁等等这些操作。</p> <p>通常有序的集合都是通过搜索树来实现的，无论是二分搜索树还是平衡二叉树它们都是搜索树，因为搜索树就有这样的优势，它可以实现有序的集合，对于有些问题集合的有序性是非常重要的。<br>
在另一些问题中完全没有必要使用有序集合，比如仅仅是处理放重复元素的问题上，根本利用不到集合的有序性，完全可以使用无序的集合来解决这个问题。</p> <p>对于无序的集合其实还是有更好的解决方案的，那就是基于哈希表的实现，对于哈希表来说，相应的增删查这样的操作其实比搜索树还要快。<br>
其实对于搜索树的实现来说如果它保持了有序性，那么它的能力其实也会更大，这个能力就表现在很轻易的查询到最大最小元素，或者某一个元素的前一个元素和后一个元素等等。<br>
当然轻易完成这些操作是有代价的，这个代价其实就在时间复杂性上，它是稍微差于哈希表的。</p> <h3 id="多重集合"><a href="#多重集合" class="header-anchor">#</a> 多重集合</h3> <p>对于集合来说在大多数情况下是不希望有重复元素的，但是在有些情况下也希望有集合可以容纳重复的元素，在这种情况下就称之为多重集合(MultipleSet)。<br>
多重集合具体的实现也非常简单，只需要在允许重复的二分搜索树上进行包装一下一下即可。要清楚你所解决的问题是否需要使用多重集合，多重集合是根据业务场景所决定的，通常使用集合的大多数情况下还是选择不包含重复元素的集合。</p></div></div> <div class="page-edit"><!----> <div class="tags"><a href="/tags/?tag=%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84" title="标签">#数据结构</a></div> <div class="last-updated"><span class="prefix">上次更新时间:</span> <span class="time">10年18月2023日 01时57分53秒</span></div></div> <div class="page-nav-wapper"><div class="page-nav-centre-wrap"><a href="/pages/67506300330/" class="page-nav-centre page-nav-centre-prev"><div class="tooltip">封装自己的专属二分搜索树篇下</div></a> <a href="/pages/3284303033/" class="page-nav-centre page-nav-centre-next"><div class="tooltip">封装自己的专属映射Map</div></a></div> <div class="page-nav"><p class="inner"><span class="prev">
        ←
        <a href="/pages/67506300330/" class="prev">封装自己的专属二分搜索树篇下</a></span> <span class="next"><a href="/pages/3284303033/"> 封装自己的专属映射Map </a>
        →
      </span></p></div></div></div> <div class="article-list"><div class="article-title"><a href="/archives/" class="iconfont icon-bi">最近更新</a></div> <div class="article-wrapper"><dl><dd>01</dd> <dt><a href="/pages/45343271027/"><div>01.数据结构导论一览.md</div></a> <span>10-16</span></dt></dl><dl><dd>02</dd> <dt><a href="/pages/38850370637/"><div>30.2023年06月04日.md</div></a> <span>06-04</span></dt></dl><dl><dd>03</dd> <dt><a href="/pages/74707370537/"><div>08.与测量相关.md</div></a> <span>05-06</span></dt></dl> <dl><dd></dd> <dt><a href="/archives/" class="more">更多文章&gt;</a></dt></dl></div></div> </main></div> <div class="footer"><!----> 
  Theme by
  <a href="https://github.com/xugaoyi/vuepress-theme-vdoing" target="_blank" title="本站主题">Vdoing</a> 
    | Copyright © 2017-2023
    <span class="link">aiyoudiao 码二</span> <span>备案号：</span> <a href="https://beian.miit.gov.cn/#/Integrated/index" target="_blank" title="备案号">鄂ICP备2022002654号-1</a></div> <div class="buttons"><div title="返回顶部" class="button blur go-to-top iconfont icon-fanhuidingbu" style="display:none;"></div> <div title="去评论" class="button blur go-to-comment iconfont icon-pinglun" style="display:none;"></div></div> <!----> <!----> <!----></div><div class="global-ui"><div></div><APlayer audio="" fixed="true" theme="#b7daff" loop="loop" order="list" preload="auto" volume="0.7" mutex="true" lrc-type="3" list-max-height="250" storage-name="vuepress-plugin-meting" id="aplayer-fixed"></APlayer><div id="VuepressPluginLive2d"></div></div></div>
    <script src="/assets/js/app.bd2fbc77.js" defer></script><script src="/assets/js/3.72c9c947.js" defer></script><script src="/assets/js/141.1f70e1c7.js" defer></script><script src="/assets/js/42.4251ca36.js" defer></script>
  </body>
</html>
